BZOJ-3172: [Tjoi2013]单词

[文章目录]

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;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注