POJ 1625 Censored! AC自動機+DP+高精度 *

題目位址：http://poj.org/problem?id=1625

一樣是拿母串在trie上搜尋，且不經過危險節點

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<map>
#include<string>
#include<vector>
using namespace std;
typedef long long LL;
struct BigInteger{
    int num[300];  
    int len;
    BigInteger(){  
        memset(num,0,sizeof(num)); len=0;  
    }  
    void output(){  
        for(int i=len-1;i>=0;i--)  
            cout<<num[i];  
        cout<<endl;  
    }  
};
BigInteger operator + (BigInteger s1,BigInteger s2)  
{  
    if(s1.len<s2.len)  
    {  
        BigInteger temp=s1;  
        s1=s2;  
        s2=temp;  
    }  
    int k=0;  
    for(int i=0,j=0;i<s1.len;i++,j++)  
    {  
        k+=s1.num[i]+s2.num[j];  
        s1.num[i]=k%10;  
        k/=10;  
    }  
    while(k)  
    {  
        s1.num[s1.len++]=k%10;  
        k/=10;  
    }  
    return s1;  
}
const int letter=55;
const int INF=0x3f3f3f3f;
struct Node{
	Node *pChilds[letter],*pPrev;
	bool bBadNode;
}tree[100+5];
char patten[50+5];
char str[50+5];
map<char,int> idx;
BigInteger d[50+5][100+5];
int nNode,N,M,P;
//d[i][j]要長度為i到達節點j，也即是tree[j] 字元串個數 
void Insert(Node* root,char* s)
{
	for(int i=0;s[i];i++)
	{
		if(root->pChilds[idx[s[i]]]==NULL)
			root->pChilds[idx[s[i]]]=tree+nNode++;
		root=root->pChilds[idx[s[i]]];
	}
	root->bBadNode=true;
}
void BuildDfa()
{
	for(int i=0;i<N;i++)
		tree[0].pChilds[i]=tree+1;
	tree[1].pPrev=tree;
	tree[0].pPrev=NULL;
	queue<Node*> Q;
	Q.push(tree+1);
	while(!Q.empty())
	{
		Node* root=Q.front(); Q.pop();
		for(int i=0;i<N;i++)
		{
			Node* p=root->pChilds[i];
			if(p==NULL) continue;
			Node* pPrev=root->pPrev;
			while(pPrev!=NULL){
				if(pPrev->pChilds[i]!=NULL){
					p->pPrev=pPrev->pChilds[i];
					if(p->pPrev->bBadNode) p->bBadNode=true;
					break;
				}
				else pPrev=pPrev->pPrev;
			}
			Q.push(p);
		}
	}
}
int main()
{
	scanf("%d%d%d",&N,&M,&P);
	scanf("%s",str);
	for(int i=0;str[i];i++) idx[str[i]]=i;
	nNode=2;
	for(int i=0;i<P;i++){
		scanf("%s",patten);
		Insert(tree+1,patten);
	}
	BuildDfa();
	
	d[0][1].num[d[0][1].len++]=1;
	for(int i=0;i<M;i++)
	for(int j=1;j<nNode;j++)
	{
		if(tree[j].bBadNode) continue;
		for(int k=0;k<N;k++)
		{
			Node* pPrev=tree+j;
			while(pPrev){
				if(pPrev->pChilds[k]!=NULL){
					if(pPrev->pChilds[k]->bBadNode) break;
					int son=pPrev->pChilds[k]-tree;
					d[i+1][son]=d[i+1][son]+d[i][j];
					break;
				} 
				pPrev=pPrev->pPrev;
			} 
		}	
	}
	
	BigInteger result[105];
	int k=0;
    result[0].num[result[0].len++]=0;
    for(int i=1;i<nNode;i++)
         k++,result[k]=d[M][i]+result[k-1];
    result[k].output();
	
	return 0;
}