POJ - 2778 DNA Sequence AC自动机+矩阵快速幂 经典好题

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
using namespace std;
const int maxn =  1005;
const int mod = 100000;
int trie[maxn][5]; //字典树
int cntword[maxn];  //记录该单词出现次数
int fail[maxn];     //失败时的回溯指针
int cnt = 0;//结点个数
int mp[128];
bool tag[maxn];//表示结点是否为病毒
struct Mat {
	ll m[105][105];
};
int n;
Mat mul(Mat x,Mat y) {
	Mat c;
	for(int i=0; i<cnt; i++) {
		for(int j=0; j<cnt; j++) {
			c.m[i][j] = 0;
		}
	}
	for(int i=0; i<cnt; i++) {
		for(int j=0; j<cnt; j++) {
			for(int k=0; k<cnt; k++) {
				c.m[i][j] = (c.m[i][j]+ x.m[i][k]*y.m[k][j]);
			}
			c.m[i][j]%=mod;
		}
	}
	return c;
}
Mat pow(Mat x,int y) { //求矩阵x的y次幂
	Mat ans;
	for(int i=0; i<cnt; i++)
		for(int j=0; j<cnt; j++)
			if(i==j)ans.m[i][i] = 1;
			else ans.m[i][j] = 0;//防止多次输入，清零
	while(y) {
		if(y&1)ans = mul(ans,x);
		x = mul(x,x);
		y>>=1;
	}
	return ans;//返回ans
}
void insertWords(char s[],int len) {
	int root = 0;
	for(int i=0; i<len; i++) {
		int next = mp[s[i]];
		if(trie[root][next]==0) {
			trie[root][next] = cnt,cnt++;
		}
		root = trie[root][next];
	}
	tag[root] = true;
}
void getFail() {
	queue <int>q;
	while(!q.empty())q.pop();
	for(int i=1; i<5; i++) {   //将第二层所有出现了的字母扔进队列
		if(trie[0][i]) {
			fail[trie[0][i]] = 0;
			q.push(trie[0][i]);
		}
	}
//fail[now]    ->当前节点now的失败指针指向的地方
////tire[now][i] -> 下一个字母为i+'a'的节点的下标为tire[now][i]
	while(!q.empty()) {
		int now = q.front();
		q.pop();
		for(int i=1; i<5; i++) {
			if(trie[now][i]) {
				fail[trie[now][i]] = trie[fail[now]][i];
				q.push(trie[now][i]);
			} else {
				trie[now][i] = trie[fail[now]][i];
				tag[now] = tag[now]||tag[fail[now]];
                                //后缀为病毒则now为病毒
			}
		}
	}
}
void query() {
	Mat m1;
	for(int i=0; i<cnt; i++) {
		for(int j=0; j<cnt; j++) {
			m1.m[i][j] = 0;
		}
	}
	ll as = 0;
	for(int i=0; i<cnt; i++) { //遍历文本串
		if(!tag[i]) {
			for(int j=1; j<5; j++) {
				if((!tag[trie[i][j]])) {
					m1.m[i][trie[i][j]]++;//m1[i][j] 表示 i 到 j 一步有多少种走法
				}
			}
		}
	}

	m1 = pow(m1,n);
	for(int i=0; i<cnt; i++) {
		as=(as+m1.m[0][i]);
	}

	printf("%lld\n",as%mod);
}
char s[12];
int main() {
	int nn;
	mp['A'] = 1;
	mp['C'] = 2;
	mp['T'] = 3;
	mp['G'] = 4;
	scanf("%d %d",&nn,&n);
	memset(trie,0,sizeof(trie));
	memset(tag,false,sizeof(tag));
	cnt = 1;

	for(int i=0; i<nn; i++) {
		scanf("%s",s) ;//输入单词
		insertWords(s,strlen(s));
	}
	fail[0] = 0;
	getFail();
	query();

	return 0;
}
/*
12 2000000000
A
AT
AT
TT
CC
AG
ATCGG
CTAA
GTCA
GTCA
ATC
CTG
*/