题目链接
两个一个递归方式一个非递归
HiHocoder
#include<bits/stdc++.h> using namespace std; #define maxn 100010 struct ac{ ],fa; }tre[maxn*]; ,len=; string s; void updata(int x,int y){ if(x>=s.size()) return ; int k=s[x]-'a'; int i; if(tre[y].nex[k]){ i=tre[y].nex[k]; tre[i].sum++; updata(++x,i); }else{ tre[y].nex[k]=++tot; tre[tot].sum=; i=tot; updata(++x,i); } ){ tre[i].fa++; } } int query(int x,int y){ int k=s[x]-'a'; ){ int i=tre[y].nex[k]; return tre[i].sum; } if(tre[y].nex[k]){ return query(++x,tre[y].nex[k]); } ; } int main(){ memset(tre,,sizeof(tre)); int n,m; cin>>n; ;j<n;j++){ cin>>s; updata(,); } cin>>m; ;j<m;j++){ cin>>s; printf(,)); } } /* 5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab 求前缀 1 0 3 0 0 */
HDU
#include<bits/stdc++.h> using namespace std; #define maxn 100000 ][]; ,tot=; struct ac{ ],fa,c; void init(){ sum=;fa=; memset(nex,,sizeof(nex)); } }tre[maxn*]; void add(char s[]){ ,j; ; while(s[i]){ int k=s[i]-'a'; if(tre[z].nex[k]){ j=tre[z].nex[k]; tre[j].sum++; z=j; }else{ tre[z].nex[k]=++tot; j=tot; tre[j].init(); tre[j].sum=; z=j; } i++; } tre[z].fa++; } bool query(char s[]){ ,j,z=; while(s[i]){ int k=s[i]-'a'; ) ; z=tre[z].nex[k]; i++; } ; ; } bool query1(char s[]){ ,j,z=; while(s[i]){ int k=s[i]-'a'; z=tre[z].nex[k]; if(tre[z].fa){ )) ; } i++; } ; } int main(){ ]); ;j<len;j++){ if(query1(a[j])){ cout<<a[j]<<endl; } } }