poj 1625 Censored! AC自动机+dp+高精度

题意：

给p个模式串，求长度为m的所有串中不含任意模式串的串的个数。

分析：

这道题不让求模，所以要用高精度，但是在矩阵乘法里用高精度花销太大，好在长度m不大，可以一步一步dp出来。在dp里加个高精度是个很有意思的事情，详见代码。

代码：

//poj 1625
#include <iostream>
#include <queue>
using namespace std;

int map[300];
int n,m,p,len;
char s[64];
int alphabet_len,index;
queue<int> Q; 
int dp[51][110][110];
 
struct Node
{
	int s[64],fail;
	bool word;		
}a[64*64];

void insert(int h,int k)
{
	if(k==len){
		a[h].word=true;
		return ;
	}
	int p=map[s[k]+128];
	if(!a[h].s[p])
		a[h].s[p]=++index;
	insert(a[h].s[p],k+1);
}

void build_AC_Automation()
{
	while(!Q.empty()) Q.pop();	
	Q.push(0);
	while(!Q.empty()){
		int h=Q.front();Q.pop();
		for(int k=0;k<alphabet_len;++k)
			if(a[h].s[k]){
				Q.push(a[h].s[k]);
				if(h) a[a[h].s[k]].fail=a[a[h].fail].s[k];
				if(a[a[a[h].s[k]].fail].word==true)
					a[a[h].s[k]].word=true;
			}else
				a[h].s[k]=a[a[h].fail].s[k];
	}
}

void add(int *a,int *b)
{
	int p,i;
	for(p=i=0;i<100;++i){
		a[i]=a[i]+b[i]+p;
		p=a[i]/10;
		a[i]%=10;
	}	
}

void print(int *a)
{
	int i;
	for(i=100;i>=0;--i)
		if(a[i]) break;
	if(i<0)
		printf("0\n");
	else{
		for(int j=i;j>=0;--j)
			printf("%d",a[j]);
		printf("\n");
	}
}
int main()
{
	scanf("%d%d%d",&n,&m,&p);
	getchar();
	gets(s);
	memset(map,-1,sizeof(map));
	alphabet_len=0;
	for(int i=0;s[i]!='\0';++i){
		int ss=s[i]+128;
		if(map[ss]==-1)
			map[ss]=alphabet_len++;
	}
	memset(a,0,sizeof(a));
	index=0;
	while(p--){
		gets(s);
		len=strlen(s);
		insert(0,0);
	}
	build_AC_Automation();
	memset(dp,0,sizeof(dp));
	int i,j,k;
	for(i=0;i<=index;++i)
		if(a[i].word==false)
			dp[0][i][0]=1;
	for(k=1;k<=m;++k)
		for(i=0;i<=index;++i)
			for(j=0;j<alphabet_len;++j){
				int next_i=a[i].s[j];
				if(a[i].word==false&&a[next_i].word==false)
					add(dp[k][i],dp[k-1][next_i]);
			}
	print(dp[m][0]);
	return 0;
}
 

poj 1625 Censored! AC自动机+dp+高精度

原文：http://blog.csdn.net/sepnine/article/details/44653559