[文章目录]
Description
某人读论文，一篇论文是由许多单词组成。但他发现一个单词会在论文中出现很多次，现在想知道每个单词分别在论文中出现多少次。N<=200,单词长度不超过10^6
一开始写了个AC自动机，然后发现WA？？？理论上应该T的。然后我们发现所求的ans其实就是有多少个子串和该单词相同，所以我们考虑，什么样的子串能与单词相同。发现fail指针指向该单词结尾的子串结尾，或者是fail的fail指向，或者是......，所以，我们将所有单词trie树路径上的点的cnt++然后按照bfs逆序进行累加。
第一次写fail指针，嘻嘻嘻。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char st[200000001];
int n,now=1,num[300],flag[300];
struct trie
{
trie *ch[26],*fail;
int cnt;
trie()
{
memset(ch,0,sizeof(ch));
fail=NULL;
cnt=0;
}
void insert(int l,int r,trie *&pos)
{
trie *p=this;
while(l<=r)
{
if(!p->ch[st[l]-'a'])
p->ch[st[l]-'a']=new trie();
p=p->ch[st[l]-'a'];p->cnt++;
l++;
}
pos=p;
}
void build_ac_auto()
{
static trie *q[1001000];
static int h=1,t=0;
for(int i=0;i<26;i++)
if(this->ch[i])
this->ch[i]->fail=this,
q[++t]=this->ch[i];
while(h<=t)
{
trie *x=q[h];h++;
for(int i=0;i<26;i++)
if(x->ch[i])
{
trie *p=x->fail;
while(p!=this&&!p->ch[i])
p=p->fail;
if(p->ch[i]) p=p->ch[i];
x->ch[i]->fail=p;
q[++t]=x->ch[i];
}
}
for(int i=t;i;i--)
q[i]->fail->cnt+=q[i]->cnt;
}
}*root=new trie(),*pos[210];
void dfs(trie *x)
{
puts("in");
for(int i=0;i<26;i++)
if(x->ch[i]!=NULL)
printf("in%d\n",i),dfs(x->ch[i]);
puts("out");
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",st+now);
int len=strlen(st+1);
root->insert(now,len,pos[i]);
now=len+1;
}
root->build_ac_auto();
for(int i=1;i<=n;i++) printf("%d\n",pos[i]->cnt);
return 0;
}