首页 > 代码库 > BZOJ 3172: [Tjoi2013]单词 [AC自动机 Fail树]
BZOJ 3172: [Tjoi2013]单词 [AC自动机 Fail树]
3172: [Tjoi2013]单词
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 3198 Solved: 1532
[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
本题的意思是说文本就是那些单词组成的.......(中间会有空格吧)
如果朴素做法建一个AC自动机然后一个个单词当做文本来匹配(走，cnt++)时间复杂度受不了】
于是发现有个神奇的地方，匹配的模式同样也是文本，建AC自动机的时候已经走过一次了啊！
Trie树ins的时候经过节点就cnt++，(也就是说这个模板能匹配到当前插入的文本)
然后统计每个单词终点节点的Fail树中子树cnt和就可以了
(因为“某个结点所对应的字符串肯定是其后代结点所对应的字符串的后缀”啊)
PS：如何统计Fail子树和？队列中正好是BFS序，队列从后往前更新fail指针的cnt就可以了
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N=1e6+5,M=205;int n;char s[N];struct node{ int ch[26],fail,cnt;}t[N];int pos[M],sz;void ins(char s[],int &x){ int u=0,n=strlen(s+1); for(int i=1;i<=n;i++){ int c=s[i]-‘a‘; if(!t[u].ch[c]) t[u].ch[c]=++sz; u=t[u].ch[c]; t[u].cnt++; } x=u;}int q[N],head,tail;void getFail(){ head=tail=1; for(int i=0;i<26;i++) if(t[0].ch[i]) q[tail++]=t[0].ch[i]; while(head!=tail){ int u=q[head++]; for(int i=0;i<26;i++){ int &v=t[u].ch[i]; if(!v) {v=t[t[u].fail].ch[i];continue;} t[v].fail=t[t[u].fail].ch[i]; q[tail++]=v; } } for(int i=tail-1;i>=1;i--) t[t[q[i]].fail].cnt+=t[q[i]].cnt;}int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%s",s+1); ins(s,pos[i]); } getFail(); for(int i=1;i<=n;i++) printf("%d\n",t[pos[i]].cnt);}
BZOJ 3172: [Tjoi2013]单词 [AC自动机 Fail树]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。