BZOJ 12 HNOI 2004 L 언어 AC 자동기(Trie 트리) + 동적 기획

제목 대의: 단어표와 m개의 문자열을 정하여 모든 문자열의 가장 긴 접두사를 묻는다. 이 접두사를 만족시키면 일부 문자열로 나누어 이 문자열이 단어표에 나타난 적이 있다.
더 이상 데이터 범위를 잘못 보지 못하겠어...트리로 해결할 수 있는 문제를 AC자동기로 썼어...
AC 로봇의 각 단어가 있는 노드에 단어표의 단어를 모두 삽입하여 해당 단어의 길이를 기록합니다.
그리고 모든 문자열에 대해 f[i]로 길이가 i인 접두사를 단어표의 단어 달리기 AC 자동기로 분할할 수 있는지 여부를 표시합니다
일치하는 노드마다 이 노드에서 루트로의fail 경로에 있는 모든len f[i]|=f[i-len]
가장 큰 f[i]를 찾으면 답입니다.
단어 길이가 최대 10이니까 트리로 바로 폭력을 가하면 돼요.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 1050000
using namespace std;
struct Trie{
	int len;
	Trie *fail,*son[26];
	void* operator new (size_t size);
}*root,*mempool,*C;
int n,m;
char s[M];
void* Trie :: operator new (size_t size)
{
	if(C==mempool)
	{
		C=new Trie[1<<15];
		mempool=C+(1<<15);
		memset(C,0,sizeof(Trie)*(1<<15) );
	}
	return C++;
}
void Insert(Trie*&p,char *pos,int dpt)
{
	if(!p) p=new Trie;
	if(!*pos)
	{
		p->len=dpt;
		return ;
	}
	Insert(p->son[(*pos)-'a'],pos+1,dpt+1);
}
void BFS()
{
	static Trie* q[1<<16];
	static unsigned short r,h;
	int i;Trie *temp;
	for(i=0;i<26;i++)
		if(temp=root->son[i])
		{
			temp->fail=root;
			q[++r]=temp;
		}
	while(r!=h)
	{
		Trie *p=q[++h];
		for(i=0;i<26;i++)
			if(p->son[i])
			{
				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];
			}
	}
}
int Aho_Corasick_Automaton()
{
	int i,re=0;
	Trie *p=root,*temp;
	static bool f[M];f[0]=1;
	for(i=1;s[i];i++)
	{
		f[i]=0;
		while( p!=root && !p->son[s[i]-'a'] )
			p=p->fail;
		if(p->son[s[i]-'a'])
		{
			p=p->son[s[i]-'a'];
			for(temp=p;temp!=root;temp=temp->fail)
				if(temp->len)
				{
					f[i]|=f[i-temp->len];
					if(f[i]) break;
				}
		}
		if(f[i]) re=i;
	}
	return re;
}
int main()
{
	int i;
	cin>>n>>m;
	for(i=1;i<=n;i++)
		scanf("%s",s+1),Insert(root,s+1,0);
	BFS();
	for(i=1;i<=m;i++)
	{
		scanf("%s",s+1);
		cout<<Aho_Corasick_Automaton()<<endl;
	}
}