2755: [TJOI2013]单词
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 6 Solved: 3
[Submit][Status][Web Board]
Description
某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次
Input
第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6
Output
输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a
aa
aaa
Sample Output
6
3
1
HINT
Source
题解:
求出fail树以后。。。
对每个串的每个节点打标记
然后输出每个串终点子树的标记个数和
#include<iostream>
#include<cstring>
#include<cstdio>
#define maxn 1000001
using namespace std;
int n,tot;
int sum[maxn],fai[maxn],son[maxn][],pos[],lis[maxn];
char s[maxn];
void insert(int x)
{
scanf("%s",s+);
int p=,nn=strlen(s+);
for (int i=; i<=nn; i++)
{
if (!son[p][s[i]-'a']) son[p][s[i]-'a']=++tot;
p=son[p][s[i]-'a'];
sum[p]++;
}
pos[x]=p;
}
void failed()
{
int head=,tail=; lis[]=; fai[]=-;
int a;
while (head<tail)
{
int now=lis[++head];
for (int i=;i<;i++)
{
if (son[now][i])
{
lis[++tail]=son[now][i];
a=fai[now];
while (a!=-&&!son[a][i]) a=fai[a];
if (a>=) fai[son[now][i]]=son[a][i];
else fai[son[now][i]]=;
}
}
}
for (int i=tail; i>=; i--)
sum[fai[lis[i]]]+=sum[lis[i]];
}
int main()
{
cin>>n; tot=;
for (int i=; i<=n; i++) insert(i);
failed();
for (int i=; i<=n; i++) printf("%d\n",sum[pos[i]]);
}