首页 > 分享 > nyoj685查找字符串(字典树)

nyoj685查找字符串(字典树)

#include<stdio.h>//685查找字符串

struct Trie{

int count;

Trie *next[30];

};

Trie *root;;

int turn(char c)//把字符转换成数组序号

{

if(c>='a' && c<='z')

return c-'a';

else if(c=='@')

return 26;//@

else

return 27;// +

}

void insert(char *s)//插入一个字符串

{

if(root==NULL || *s=='')

return ;

int i;

Trie *p=root;

while(*s!='')

{

if(p->next[turn(*s)]==NULL)//字符串不存在,则创建

{

Trie *temp=new Trie;

for(i=0;i<30;i++)

temp->next[i]=NULL;

temp->count=0;//付初值0

p->next[turn(*s)]=temp;

}

p=p->next[turn(*s)];

s++;

}

p->count++;

}

int Tfind(char *s)

{

Trie *p=root;

while(p!=NULL && *s!='')

{

p=p->next[turn(*s)];

s++;

}

return p==NULL?0:p->count;//注意如果字符串不存在也是0;不存在时候p==NULL

}

void del(Trie *p)//删除,oj提交的时候建议不删除,因为这个也耗时间。系统自动会回收,但是自己写的时候要注意。

{

int i;

for(i=0;i<30;i++)

{

if(p->next[i]!=NULL)

del(p->next[i]);

}

delete p;

}

int main()

{

int T;

int n,m;

int i;

char s[20];

scanf("%d",&T);

getchar();

while(T--)

{

root=new Trie;

for(i=0;i<30;i++)

root->next[i]=NULL;

root->count=0;

scanf("%d%d",&n,&m);

for(i=0;i<n;i++)

{

scanf("%s",s);

insert(s);

}

while(m--)

{

scanf("%s",s);

printf("%dn",Tfind(s));

}

del(root);

}

return 0;

}

我也是即学即用。今天刚看的字典树,今天用上的第一个程序、自己理解不难,我就不加上注释了。

相关知识

nyoj685查找字符串(字典树)
Wireshark搜索/查找字符串失败
字符串查找、错误信息、字符分类函数
作业打卡 设置密码 &水仙花数& 查找字符串
算法的艺术
字符串
寻找字符串
mysql创建索引的原则 mysql创建索引的语法
字符串(C# 编程指南)
字符串查询算法

网址: nyoj685查找字符串(字典树) https://m.huajiangbk.com/newsview105051.html

所属分类:花卉
上一篇: JNI 提示
下一篇: 字符串查询算法