题目链接
两个一个递归方式一个非递归
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;
}
}
}