链接:http://poj.org/problem?id=2778
题意:给定不超过10串，每串长度不超过10的灾难基因；问在之后给定的长度不超过2e9的基因长度中不包含灾难基因的基因有多少中?
DNA:只含'A','T','C','G'四种字符；
思路:这并不是很裸的ac自动机。。没有很明显的文本串匹配过程，但是我们能过通过对灾难基因建好Trie，在跑一下失配边时需要初始化状态转移矩阵了；
状态矩阵:每一次都可以往下一个位置走四个方向，但是要求不能走到单词节点。
(mat[i][j]) ^n: 表示走了n步，i 表示从那个节点开始走，j表示最终的字符(并不是特点的字符，可以表示多个合法的字符)；
即:第i个节点到第v个节点之间一步走有几种方法
$ ans = \sum \limits _{i=0}^{\rm size} mat\left [0 \right ]\left [ i \right ]$
#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 #define sqr(a) (a)*(a) typedef pair<int,int> PII; #define A first #define B second #define MK make_pair typedef __int64 ll; template<typename T> void read1(T &m) {T x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}m = x*f; } template<typename T> void read2(T &a,T &b){read1(a);read1(b);} template<typename T> void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);} template<typename T> void out(T a) {if(a>9) out(a/10);putchar(a%10+'0'); } int T,kase = 0,i,j,k,n,m,top; #define mod 100000 struct Matrix{int d[107][107];Matrix(int r = 0){MS0(d);if(r){for(int i = 0;i < top;i++)d[i][i] = 1;}}Matrix operator*(const Matrix& a)const{Matrix ans;for(int i = 0;i < top;i++)for(int j = 0;j < top;j++){for(int k = 0;k < top;k++)ans.d[i][j] = (ans.d[i][j]+1LL*d[i][k]*a.d[k][j]) % mod;}return ans;} }; Matrix Pow(Matrix a,ll m) {Matrix ans(1);while(m){if(m&1) ans = ans*a;a = a*a;m >>= 1;}return ans; } int h[128]; const int sigma_size = 4; const int maxn = 107; struct Aho_Corasick{int ch[maxn][sigma_size];int val[maxn],f[maxn],last[maxn],cnt[maxn];int sz;map<string,int> ms;Aho_Corasick(){}void init(){sz = 1;val[0] = 0; MS0(ch[0]);MS0(cnt);ms.clear();}int idx(char c){return h[c];}void Insert(char *s,int v){int u = 0,n = strlen(s);for(int i = 0;i < n;i++){int c = idx(s[i]);if(!ch[u][c]){MS0(ch[sz]);val[sz] = 0;ch[u][c] = sz++;}u = ch[u][c];}val[u] = v;}void getFail(){queue<int> q;f[0] = 0;//初始化队列for(int c = 0;c < sigma_size;c++){int u = ch[0][c];if(u) { f[u] = 0; q.push(u); last[u] = 0;}}while(!q.empty()){int r = q.front();q.pop();for(int c = 0;c < sigma_size;c++){int u = ch[r][c];if(!u) {ch[r][c] = ch[f[r]][c]; continue;}//实现压缩 q.push(u);int v = f[r];while(v && !ch[v][c]) v = f[v];f[u] = ch[v][c];last[u] = val[f[u]]?f[u]:last[f[u]];}}}//从文本串中找模板; Matrix Find(){Matrix ans;for(int i = 0;i < sz;i++){if(val[i] || last[i]) continue;//合法即可for(int j = 0;j < 4;j++){ //每个节点都可以生成4个节点int v = ch[i][j];if(val[v] || last[v]) continue;ans.d[i][v]++; //也可以表示第i个节点到第v个节点之间一步走有几种方法;}}return ans;} }ac; char p[15]; int main() {ll n,m;//freopen("data.txt","r",stdin);//freopen("out.txt","w",stdout);h['A'] = 0;h['C'] = 1;h['T'] = 2;h['G'] = 3;ac.init();read2(n,m);rep1(i,1,n){scanf("%s",p);ac.Insert(p,i);}top = ac.sz;ac.getFail();Matrix ans = ac.Find();ans = Pow(ans,m);int cnt = 0;rep0(i,0,top)cnt += ans.d[0][i];printf("%d\n",cnt%mod);return 0; }