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 提示 |
下一篇: 字符串查询算法 |
