用\(p[i]\)来表示经过节点\(i\)的字符串个数。
那么节点\(u\)的答案就是fail树上，以\(u\)为根的子树的\(p\)之和。
由于我们已经计算了\(p[i]\)，所以字符串\(i\)作为模式串本身&模式串前缀的情况已经考虑了。还需考虑\(i\)作为模式串后缀的情况，而只有fail树上子树\(i\)的节点才有\(i\)这个后缀，所以累加即可。
点击查看代码
#include<bits/stdc++.h>
#define T 210
#define N 1000010
#define S 26
using namespace std;
int n,tr[N][S],fail[N],cnt,ans[N],pos[T],deg[N];
queue<int> q;
string s;
void ins(string s,int num){
int p=0;
for(char i:s){
int c=i-'a';
if(!tr[p][c]) tr[p][c]=++cnt;
p=tr[p][c];
ans[p]++;
}
pos[num]=p;
}
void get_fail(){
for(int i=0;i<26;i++)
if(tr[0][i]) q.push(tr[0][i]);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=0;i<26;i++){
if(tr[u][i])
fail[tr[u][i]]=tr[fail[u]][i],
q.push(tr[u][i]),deg[fail[tr[u][i]]]++;
else tr[u][i]=tr[fail[u]][i];
}
}
}
void topo(){
for(int i=1;i<=cnt;i++) if(!deg[i]) q.push(i);
while(!q.empty()){
int t=q.front();
q.pop();
ans[fail[t]]+=ans[t],deg[fail[t]]--;
if(!deg[fail[t]]) q.push(fail[t]);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
ins(s,i);
}
get_fail();
topo();
for(int i=1;i<=n;i++)
cout<<ans[pos[i]]<<"\n";
return 0;
}
还有一种方法可以不用拓扑排序，就是用数组来模拟get_fail()中的队列，这样队头到队尾一定是BFS序，所以反过来，从队尾到队头一定是一个拓扑序，所以更新的时候不用拓扑排序，仅需用一个循环，从队尾遍历到队头，更新答案即可。
点击查看代码
#include<bits/stdc++.h>
#define T 210
#define N 1000010
#define S 26
using namespace std;
int n,tr[N][S],fail[N],cnt,ans[N],pos[T],q[N];
string s;
void ins(string s,int num){
int p=0;
for(char i:s){
int c=i-'a';
if(!tr[p][c]) tr[p][c]=++cnt;
p=tr[p][c];
ans[p]++;
}
pos[num]=p;
}
void get_fail(){
int head=1,tail=0;
for(int i=0;i<26;i++)
if(tr[0][i]) q[++tail]=tr[0][i];
while(head<=tail){
int u=q[head++];
for(int i=0;i<26;i++){
if(tr[u][i])
fail[tr[u][i]]=tr[fail[u]][i],
q[++tail]=tr[u][i];
else tr[u][i]=tr[fail[u]][i];
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>s;
ins(s,i);
}
get_fail();
for(int i=cnt;i>=1;i--) ans[fail[q[i]]]+=ans[q[i]];
for(int i=1;i<=n;i++)
cout<<ans[pos[i]]<<"\n";
return 0;
}