BZOJ 3172 Tjoi2013 單詞 fail樹

BZOJ 3172 Tjoi2013 單詞 fail樹

原來正解是fail樹……難怪後綴數組被卡成這樣

首先我們將給出的n個串構建AC自動機

樸素的做法是對於每個串將這個串每個節點沿著fail指針掃一遍，將路徑上的所有點的cnt++

但是這樣做會TLE

我們不妨反向思考 fail指針反向後是一棵樹 沿著fail指針掃一遍就是沿著樹邊向根掃一遍

只在插入時將每個串的每個節點cnt++ 那麼每個串終點所在fail樹的子樹中cnt的總和就是這個字符串的出現次數

於是每個點記錄所在fail樹的子樹中cnt的數量 可以線性時間內出解

#include 
#include 
#include 
#include 
#define M 1001001
using namespace std;
struct Trie{
	Trie *son[26],*fail;
	int cnt;
}*root,mempool[M],*C=mempool;
int n;
Trie *pos[210];
char s[M];
void Insert(Trie* &p,char *s,Trie* &pos)
{
	if(!p) p=C++;
	p->cnt++;
	if(!*s)
	{
		pos=p;
		return ;
	}
	Insert(p->son[(*s)-'a'],s+1,pos);
}
void Build_Tree()
{
	static Trie *q[M];
	static int r,h;
	int i;
	for(i=0;i<26;i++)
		if(root->son[i])
			root->son[i]->fail=root,q[++r]=root->son[i];
	while(r!=h)
	{
		Trie *p=q[++h];
		for(i=0;i<26;i++)
			if(p->son[i])
			{
				Trie *temp=p->fail;
				while(temp!=root&&!temp->son[i])
					temp=temp->fail;
				if(temp->son[i]) temp=temp->son[i];
				p->son[i]->fail=temp;
				q[++r]=p->son[i];
			}
	}
	for(i=r;i;i--)
		q[i]->fail->cnt+=q[i]->cnt;
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		scanf(%s,s),Insert(root,s,pos[i]);
	Build_Tree();
	for(i=1;i<=n;i++)
		printf(%d
,pos[i]->cnt);
	return 0;
}