poj 2778 DNA Sequence AC自动机+矩阵幂加速

题意：

给m个模式串，问长度为n的所有串中不含所有模式串的串有几个。

分析：

构造完ac自动机后将自动机转换为状态转移矩阵，mat[i][j]表示一步从状态i到状态j的方法数。最后用矩阵幂加速。ps:求模运算很慢，尽量放在for循环外层。

代码：

//poj 2778
//sep9
#include <iostream>
#include <queue>
using namespace std;
typedef __int64 LL;
const int mod=100000;

struct node
{
	int s[4],fail;
	bool word;
}a[128];
struct MAT
{
	LL v[128][128];		
}mat,ans;

char segment[16];
int len,code[100];
int index;
queue<int> Q;

void build_trie(int h,int k)
{
	if(k==len){
		a[h].word=true;
		return ;
	}	
	int p=code[segment[k]];
	if(!a[h].s[p]) a[h].s[p]=++index;
	build_trie(a[h].s[p],k+1);
}
MAT mul(MAT x,MAT y)
{
	MAT z;
	memset(z.v,0,sizeof(z.v));
	for(int i=0;i<=index;++i)
		for(int j=0;j<=index;++j){
			for(int k=0;k<=index;++k)
				z.v[i][j]+=x.v[i][k]*y.v[k][j];
			z.v[i][j]%=mod;
		}
	return z;
}
void build_AC_Automation()
{
	int h,i;
	while(!Q.empty()) Q.pop();
	Q.push(0);
	while(!Q.empty()){
		int h=Q.front();Q.pop();
		for(i=0;i<4;++i)
			if(a[h].s[i]){
				Q.push(a[h].s[i]);
				if(h) a[a[h].s[i]].fail=a[a[h].fail].s[i];
				if(a[a[a[h].s[i]].fail].word==true) a[a[h].s[i]].word=true;
			}else if(h)
				a[h].s[i]=a[a[h].fail].s[i];
	}	
}
void build_matrix()
{
	memset(mat.v,0,sizeof(mat.v));
	for(int i=0;i<=index;++i)
		for(int j=0;j<4;++j)
			if(a[i].word==false&&a[a[i].s[j]].word==false)
				++mat.v[i][a[i].s[j]];
}
void pow_matrix(int n)
{
	memset(ans.v,0,sizeof(ans.v));	
	for(int i=0;i<=index;++i) ans.v[i][i]=1;
	while(n){
		if(n&1) ans=mul(ans,mat);
		mat=mul(mat,mat);
		n>>=1;
	}
}

int main()
{
	int m,n;
	code['A']=0;code['C']=1;code['T']=2;code['G']=3;
	scanf("%d%d",&m,&n);
	index=0;
	memset(a,0,sizeof(a));
	while(m--){
		scanf("%s",segment);
		len=strlen(segment);
		build_trie(0,0);
	}
	build_AC_Automation();
	build_matrix();
	pow_matrix(n);		
	LL sum=0;
	for(int i=0;i<=index;++i)
		sum+=ans.v[0][i];
	sum%=mod;
	printf("%I64d",sum);
	return 0;	
} 

poj 2778 DNA Sequence AC自动机+矩阵幂加速

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