题目大意:
一篇论文是由许多单词组成,现在想知道每个单词分别在论文中出现多少次.
题解:
我们首先考虑fail指针的含义
如果fail[x] = y,那么我们就知道y作为x的后缀在x中出现了一次
所以对于一般串的来说fail[x]都会在x中出现
那么我们就有siz[fail[x]] += siz[x]
其中siz表示该串在文章中出现的次数(初始值为1)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 256;
const int maxl = 1000010;
int ch[maxl][26],nodecnt;
int siz[maxl];
int mp[maxn];
void insert(int pos,char *s){
int len = strlen(s),nw = 0;
for(int i=0,c;i<len;++i){
c = s[i] - 'a';
if(ch[nw][c] == 0) ch[nw][c] = ++ nodecnt;
nw = ch[nw][c];siz[nw] ++;
}mp[pos] = nw;
}
int q[maxl],l,r,f[maxl];
int ans[maxl];
inline void build(){
f[0] = 0;l = 0;r = -1;
int u = 0;
for(int c=0;c<26;++c){
if(ch[u][c]){
f[ch[u][c]] = 0;
q[++r] = ch[u][c];
}
}
while(l <= r){
u = q[l++];
for(int c=0;c<26;++c){
int v = ch[u][c];
if(!v){
//ch[u][c] = ch[f[u]][c];
continue;
}q[++r] = v;
int x = f[u];
while(x && !ch[x][c]) x = f[x];
f[v] = ch[x][c];
}
}
for(int i=r;i>=0;--i){
siz[f[q[i]]] += siz[q[i]];
}
}
char s[maxl];
int main(){
int n;read(n);
for(int i=1;i<=n;++i){
scanf("%s",s);
insert(i,s);
}build();
for(int i=1;i<=n;++i) printf("%d
",siz[mp[i]]);
getchar();getchar();
return 0;
}