描述
http://www.lydsy.com/JudgeOnline/problem.php?id=3172
\(n\)个单词组成一篇文章,求每个单词在文章中出现的次数.
分析
这道题很像BZOJ_2434_[NOI2011]_阿狸的打字机_(AC自动机+dfs序+树状数组)
一个单词出现过,那么一定是某个单词的某个前缀的后缀,可以通过这个前缀的末尾沿着失配边找到它.我们要统计有多少点可以这样找到它.
建立fail树,很显然,单词\(x\)子树中的所有点都可以沿着失配边找到\(x\),这样我们只用记录每个点有多少次就行了.
(eg:如果文章是 a aa aaa,那么a有3次(三个单词各一次),aa有2次(第二个单词和第三个单词),aaa有1次(第三个单词)).
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+,type=;
int n,m;
char s[maxn];
struct Aho_Corasick{
int sz;
int q[maxn],val[maxn],pos[maxn],f[maxn];
int ch[maxn][type];
Aho_Corasick():sz(){memset(ch[],,sizeof ch[]);memset(val,,sizeof val);}
inline int insert(char *s){
int u=,m=strlen(s+);
for(int i=;i<=m;i++){
int c=s[i]-'a';
if(!ch[u][c]){
memset(ch[++sz],,sizeof ch[sz]); val[sz]=;
ch[u][c]=sz;
}
u=ch[u][c];
val[u]++;
}
return u;
}
inline void get_fail(){
int L=,R=;
for(int c=;c<type;c++){
int u=ch[][c];
if(u){f[u]=;q[++R]=u;}
}
while(L<=R){
int u=q[L++];
for(int c=;c<type;c++){
int t=ch[u][c];
if(!t){ch[u][c]=ch[f[u]][c];continue;}
int v=f[u];
f[t]=ch[v][c];
q[++R]=t;
}
}
for(int i=sz;i;i--) val[f[q[i]]]+=val[q[i]];
}
inline void solve(){
for(int i=;i<=n;i++) printf("%d\n",val[pos[i]]);
}
}ac;
inline void solve(){
ac.get_fail();
ac.solve();
}
inline void init(){
scanf("%d",&n);
for(int i=;i<=n;i++){
scanf("%s",s+);
ac.pos[i]=ac.insert(s);
}
}
int main(){
init();
solve();
return ;
}
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MB
Submit: 2837 Solved: 1356
[Submit][Status][Discuss]
Description
某人读论文,一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次,现在想知道每个单词分别在论文中出现多少次。
Input
第一个一个整数N,表示有多少个单词,接下来N行每行一个单词。每个单词由小写字母组成,N<=200,单词长度不超过10^6
Output
输出N个整数,第i行的数字表示第i个单词在文章中出现了多少次。
Sample Input
3
a
aa
aaa
a
aa
aaa
Sample Output
6
3
1
3
1