题目：DNA Sequence
这题做了一晚上，即使大体的思路明白了，但还是纠缠与各种细节的实现
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;#define mod 100000
#define pb push_back
struct node {int son[4],fail;bool flag;node(){memset(son,0,sizeof(son));}node(bool f):flag(f){memset(son,0,sizeof(son));}
};
vector<node> ac;
int hash[256];
struct matrix {long long a[101][101];matrix(){memset(a,0,sizeof(a));}matrix(long long p) {memset(a,0,sizeof(a));set(p);}void set(long long p) {for(int i=0;i<ac.size();++i)a[i][i]=p;}matrix operator*(const matrix &p) {matrix res;for(int i=0;i<ac.size();++i)for(int j=0;j<ac.size();++j) {for(int k=0;k<101;++k)res.a[i][j]+=this->a[i][k]*p.a[k][j];res.a[i][j]%=mod;}return res;}long long sum() {long long res=0;for(int i=0;i<ac.size();++i)res+=this->a[0][i],res%=mod;return res;}
}ans;void insert(char *str) {int p=0,i=0;while(str[p]) {if(ac[i].flag) break;//危险节点后不用再加儿子if(!ac[i].son[hash[str[p]]]) {ac[i].son[hash[str[p]]]=ac.size();ac.pb(node(false));}i=ac[i].son[hash[str[p]]];p++;}ac[i].flag=true;
}void getFail() {ac[0].fail=-1;queue<int> qu;qu.push(0);while(!qu.empty()) {int cur=qu.front();qu.pop();if(ac[cur].flag) continue;//危险节点不需要拓展子节点，或计入答案for(int i=0;i<4;++i) {int nex=ac[cur].son[i];if(nex) {qu.push(nex);int p=ac[cur].fail;while(~p&&!ac[p].son[i]) p=ac[p].fail;if(~p) ac[nex].fail=ac[p].son[i],ac[nex].flag|=ac[ac[nex].fail].flag;//若fail指向的节点是危险节点,则nex包含危险节点,不用计入答案else ac[nex].fail=0;}if(nex&&!ac[nex].flag) ++ans.a[cur][nex];else if(!nex) {int p=ac[cur].fail;while(~p&&!ac[p].son[i]) p=ac[p].fail;//遇到第一个匹配点就应跳出,而不是碰到匹配的危险节点后继续往上走,这相当于掩耳盗铃if(~p&&!ac[ac[p].son[i]].flag) ++ans.a[cur][ac[p].son[i]];//如果fail指向的节点是危险节点,就不应计入答案else if(!~p) ++ans.a[cur][0];}}}
}matrix qpow(int p) {matrix res(1);while(p) {if(p&1) res=res*ans;ans=ans*ans;p>>=1;}return res;
}int main() {ios::sync_with_stdio(false);hash['A']=0;hash['T']=1;hash['C']=2;hash['G']=3;ac.pb(node(false));int m,n;scanf("%d%d",&m,&n);char str[20];while(m--) {scanf("%s",str);insert(str);}getFail();printf("%d\n",qpow(n).sum());return 0;
}