学步园

//搜索+字典树(Trie)<br /> //维基百科关于字典树的介绍<br /> //Trie，又称单词查找树，是一种树形结构，是一种哈希树的变种。<br /> //典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。<br /> //它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。<br /> #include<cstdio><br /> #include<cstring><br /> using namespace std;<br /> int n,m,ans;<br /> char str[10];<br /> struct dic_tree//构造字典树，26叉树，根结点为空<br /> {<br /> dic_tree *node[26];//26个结点<br /> bool terminal;//表示该结点位置是否是单词的结束位<br /> dic_tree()//构造函数,初始化终点情况和结点<br /> {<br /> for(int i = 0;i < 26;++i)<br /> {<br /> node[i] = NULL;//初始化空结点,node[0]表示'a'在该单词中<br /> terminal = 0;<br /> }<br /> }<br /> }*root;//树是通过指针形式来表达的<br /> void build(dic_tree *p,char str[],int end)//生成字典树的函数<br /> {<br /> int ix = 0;<br /> while(ix < end)//循环直到读完单词最后一个字母<br /> {<br /> int c = str[ix] - 'a';<br /> if(p->node[c])//如果到node[c]连通<br /> {<br /> p = p->node[c];<br /> if(ix == end - 1)<br /> p->terminal = 1;<br /> ++ix;<br /> }<br /> else<br /> {<br /> p->node[c] = new dic_tree; //如果不连通，则在该结点生成一个26叉树<br /> p = p->node[c];<br /> if(ix == end - 1)<br /> p->terminal = 1;<br /> ++ix;<br /> }<br /> }<br /> }<br /> void search(dic_tree *p,char str[],int end)<br /> {<br /> int ix = 0;<br /> while(ix < end)<br /> {<br /> int c = str[ix] - 'a';<br /> if(p->node[c])<br /> {<br /> p = p->node[c];<br /> if(ix == end - 1 && p->terminal == 1)<br /> {<br /> --ans;<br /> p->terminal = 0;<br /> return;<br /> }<br /> ++ix;<br /> }<br /> else return;<br /> }<br /> }<br /> void release(dic_tree *p)//必须递归释放结点空间<br /> {<br /> for(int i = 0;i < 26; i++)<br /> if(p->node[i])<br /> release(p->node[i]);<br /> delete p;<br /> }<br /> void transcase(char str[])<br /> {<br /> for(int i = 0;i < strlen(str);++i)<br /> {<br /> if(str[i] >= 'A' && str[i] <= 'Z')<br /> str[i] = str[i] - 'A' + 'a';<br /> }<br /> }//转化大小写<br /> int main()<br /> {<br /> //freopen("in.txt","r",stdin);<br /> while(scanf("%d",&n))<br /> {<br /> if(n == 0) break;<br /> scanf("%d",&m);<br /> root = new dic_tree;<br /> ans = n;<br /> for(int i = 0;i < n;++i)<br /> {<br /> scanf("%s",str);<br /> transcase(str);//转换大小写<br /> build(root,str,strlen(str));//生成字典树<br /> }<br /> for(int i = 0;i < m;++i)<br /> {<br /> scanf("%s",str);<br /> transcase(str);//转换大小写<br /> search(root,str,strlen(str));//搜索字典树<br /> }<br /> printf("%d/n",ans);<br /> release(root);//记住构造树后一定要释放结点空间，否则会内存溢出<br /> }<br /> return 0;<br /> }<br />