[PKU/POJ][2778][DNA Sequence][AC自动机]

利用AC自动机构建一个 DFA， 该 DFA 不经过任何模式串。然后问题转化为在一个图上找经过 n 条边的路径条数。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef long long LL;
int n, m, cnt= 0;

LL mat[200][200]= {0};

struct Node{
	int next[4];
	int fail, flag;
	void init(){
		for( int i= 0; i< 4; ++i ) next[i]= 0;
		fail= -1; flag= 0; }
}tb[200];

inline int toInt( char ch ){
	switch( ch ){
		case 'A': return 0;
		case 'T': return 1;
		case 'G': return 2;
		case 'C': return 3;
	}
}

void insert( char* s ){
	int rt= 0;
	while( *s ){
		int t= toInt( *s );
		
		if( tb[rt].next[t]== 0 ){
			tb[++cnt].init();
			tb[rt].next[t]= cnt;
		}
		rt= tb[rt].next[t]; s++;
	}
	tb[rt].flag= 1;
}

char str[15];

int que[200], head, tail;
void bfs(){
	head= tail= 0; que[0]= 0;
	
	int p, q;
	while( head<= tail ){
		int now= que[head++];
		
		for( int t= 0; t< 4; ++t )
		if( tb[now].next[t] ){
			p= tb[now].next[t]; q= tb[now].fail;
			while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
			if( q== -1 ) tb[p].fail= 0;
			else{
				tb[p].fail= tb[q].next[t];
				tb[p].flag|= tb[ tb[p].fail ].flag;
			}
			que[++tail]= p;
		}
		else{
			q= tb[now].fail;
			while( q!= -1 && !tb[q].next[t] ) q= tb[q].fail;
			
			if( q== -1 ) tb[now].next[t]= 0;
			else tb[now].next[t]= tb[q].next[t];
		}
	}
}

inline void mult( LL x[200][200], LL y[200][200] ){
	LL z[200][200];
	for( int i= 0; i<= cnt; ++i )
	for( int j= 0; j<= cnt; ++j ){
		z[i][j]= 0;
		for( int k= 0; k<= cnt; ++k )
		z[i][j]+= x[i][k]* y[k][j];
		
		z[i][j]%= 100000;
	}
	for( int i= 0; i<= cnt; ++i )
	for( int j= 0; j<= cnt; ++j ) y[i][j]= z[i][j];
}

int main(){
	scanf("%d%d",&m, &n ); tb[0].init();
	for( int i= 0; i< m; ++i ){
		scanf("%s", str );
		insert( str );
	}
	
	bfs();
	for( int i= 0; i<= cnt; ++i )
	if( tb[i].flag== 0 )
	for( int j= 0; j< 4; ++j )
	if( tb[ tb[i].next[j] ].flag== 0 ) mat[i][ tb[i].next[j] ]++;
	
	LL ans[200][200]= {0};
	for( int i= 0; i<= cnt; ++i ) ans[i][i]= 1;
	while( n ){
		if( n& 1 ) mult( mat, ans );
		mult( mat, mat ); n>>= 1;
	}
	
	LL res= 0;
	for( int i= 0; i<= cnt; ++i )
	if( tb[i].flag== 0 ) res+= ans[0][i];
	
	printf("%I64d\n", res% 100000 );

	return 0;
}