Repository HDU - 2846 字典树
题意：给出很多很多很多很多个 单词 类似搜索引擎一下 输入一个单词 判断有一个字符串包含这个单词
思路：字典树变体，把每个单词的后缀都扔字典树里面，这里要注意dd是一个单词 但是把d 和dd都放字典树
拿d匹配这一个单词会匹配两次 所以要开个数组记录一下上一个使该位置数量加一的字符串 如果该字符串不是同一个
那就可以加加了
TLE：还是数组大小的问题 字典树有毒！因为一个字符串可以拆成很多个后缀所以必须开大，开大了就过了。。。
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=500010; 4 struct Trie{ 5 int ch[maxn][27]; 6 int num[maxn]; 7 int lastnum[maxn]; 8 int size=1; 9 void init(){ 10 memset(ch,0,sizeof(ch)); 11 memset(num,0,sizeof(num)); 12 memset(lastnum,0,sizeof(lastnum)); 13 size=1; 14 } 15 void insert(char*s,int ok){ 16 int i=0,rc=0; 17 for(;s[i]!='\0';i++){ 18 int id=s[i]-'a'; 19 //coutr<<rc<<endl; 20 if(ch[rc][id]==0){ 21 ch[rc][id]=size++; 22 } 23 rc=ch[rc][id]; 24 if(lastnum[rc]==0||lastnum[rc]!=ok)num[rc]++,lastnum[rc]=ok; 25 //cout<<" "<<num[rc]<<" "<<rc<<endl; 26 } 27 } 28 int find(char*s){ 29 int i=0,rc=0; 30 for(;s[i]!='\0';i++){ 31 int id=s[i]-'a'; 32 if(ch[rc][id]==0)return 0; 33 rc=ch[rc][id]; 34 } 35 return num[rc]; 36 } 37 }trie; 38 char s[100]; 39 char s1[100]; 40 int main(){ 41 int n; 42 trie.init(); 43 scanf("%d",&n); 44 for(int i=0;i<n;i++){ 45 scanf("%s",s); 46 int len=strlen(s); 47 for(int j=0;j<len;j++){ 48 trie.insert(s+j,i+1); 49 } 50 } 51 int t; 52 scanf("%d",&t); 53 while(t--){ 54 scanf("%s",s); 55 printf("%d\n",trie.find(s)); 56 } 57 return 0; 58 }
