AC自动机与拓扑优化(求出现次数)
cpp
int tr[N][26],cnt[N],idx,id[N],ne[N],din[N];
void insert(string &s,int pos){
int p=0;
for(int i=0;i<s.size();i++){
int v=s[i]-'a';
if(!tr[p][v])tr[p][v]=++idx;
p=tr[p][v];
}
id[pos]=p;
}
void build(){
queue<int> q;
for(int i=0;i<26;i++){
if(tr[0][i])q.push(tr[0][i]);
}
while(!q.empty()){
auto u=q.front();
q.pop();
for(int i=0;i<26;i++){
int &p=tr[u][i];
if(!p)p=tr[ne[u]][i];
else{
ne[p]=tr[ne[u]][i];
din[ne[p]]++;
q.push(p);
}
}
}
}
void query(string &s){
for(int i=0,j=0;i<s.size();i++){
int v=s[i]-'a';
j=tr[j][v];
cnt[j]++;
}
}
void topu(){
queue<int> q;
for(int i=0;i<=idx;i++){
if(din[i]==0)q.push(i);
}
while(!q.empty()){
auto u=q.front();
q.pop();
int v=ne[u];
cnt[v]+=cnt[u];
if(--din[v]==0)q.push(v);
}
}
void solve(){
int n;
cin>>n;
string s;
for(int i=0;i<n;i++){
cin>>s;
insert(s,i);
}
build();
cin>>s;
query(s);
topu();
for(int i=0;i<n;i++)cout<<cnt[id[i]]<<"\n";
}