Trie树的小应用—

题意（自己编的）：

给你一篇文章，包含n个长度为Si的单词，然后给你m组询问，每次询问一个单词在这篇文章中作为单词前缀出现的次数。n <=10^6,m<=10^6,Si<=100。

还是用字典树，在插入的时候记录每一个节点被访问的次数，在查找的时候用指针p找到当前单词，这个单词的最后一个字母到的节点所存的次数就是它作为前缀出现的次数。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int M=1e6+;

 char word[];

 int n,m,trie[M][],sum=,tim[M];

 void insert(char a[])

 {

     int len=strlen(a),p=;

     for(int i=;i<len;i++)

     {

         int ch=a[i]-'a';

         if(trie[p][ch]==)trie[p][ch]=++sum;

         p=trie[p][ch];

         //if(i!=len-1)//如果是严格前缀的话

         tim[p]++;//tim数组记录每个节点被访问过的次数

     }

 }

 int find(char a[])

 {

     int len=strlen(a),p=;

     for(int i=;i<len;i++)

     {

         int ch=a[i]-'a';

         p=trie[p][ch];

         if(p==)return ;

     }

     return tim[p];

 }

 int main()

 {

     cin>>n>>m;

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

     {

         cin>>word;

         insert(word);

     }

     for(int i=;i<=m;i++)

     {

         cin>>word;

         printf("%d\n",find(word));

     }

     return ;

 }

巴特西

Trie树的小应用——Chemist

最新文章

热门文章