距离上次做AC自动机有很久了=。=，以前这题的思路死活看不懂，现在还是觉得很好理解的。
思路参见：。
我用cnt=1表示这个节点是危险的，然后再匹配fail指针的时候，如果一个节点的前缀是危险的，那么这个节点也是危险的，这么维护即可。
顺便一提，我以前的AC自动机模板是没有build过程中失配时的nxt指针的（以前是在match的过程中体现），但是失败时候需要的nxt指针又是很好用的，因此以后的模板中在build中新增这个内容（其实上次的AC自动机DP中就已经有了）。
另外两点可能不是很重要的是：1.我的矩阵模板统一是从1开始的，而这里有0节点；2.在结构体内似乎不能直接初始化字符串= =。
代码如下（我的代码跑的有点慢。。）：
1 #include2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 const int MAX_Tot = 100 + 50; 8 const int mod = 100000; 9 10 int m,n; 11 12 void add(int &a,int b) 13 { 14 a += b; 15 if(a < 0) a += mod; 16 a %= mod; 17 } 18 19 struct matrix 20 { 21 int e[MAX_Tot][MAX_Tot],n,m; 22 matrix() {} 23 matrix(int _n,int _m): n(_n),m(_m) {memset(e,0,sizeof(e));} 24 matrix operator * (const matrix &temp)const 25 { 26 matrix ret = matrix(n,temp.m); 27 for(int i=1;i<=ret.n;i++) 28 { 29 for(int j=1;j<=ret.m;j++) 30 { 31 for(int k=1;k<=m;k++) 32 { 33 add(ret.e[i][j],1LL*e[i][k]*temp.e[k][j]%mod); 34 } 35 } 36 } 37 return ret; 38 } 39 matrix operator + (const matrix &temp)const 40 { 41 matrix ret = matrix(n,m); 42 for(int i=1;i<=n;i++) 43 { 44 for(int j=1;j<=m;j++) 45 { 46 add(ret.e[i][j],(e[i][j]+temp.e[i][j])%mod); 47 } 48 } 49 return ret; 50 } 51 void getE() 52 { 53 for(int i=1;i<=n;i++) 54 { 55 for(int j=1;j<=m;j++) 56 { 57 e[i][j] = i==j?1:0; 58 } 59 } 60 } 61 }; 62 63 matrix qpow(matrix temp,int x) 64 { 65 int sz = temp.n; 66 matrix base = matrix(sz,sz); 67 base.getE(); 68 while(x) 69 { 70 if(x & 1) base = base * temp; 71 x >>= 1; 72 temp = temp * temp; 73 } 74 return base; 75 } 76 77 char way[4] = { 'A','T','C','G'}; 78 struct Aho 79 { 80 struct state 81 { 82 int nxt[4]; 83 int fail,cnt; 84 }stateTable[MAX_Tot]; 85 86 int find(char c) { for(int i=0;i<4;i++) if(c == way[i]) return i;} 87 88 int size; 89 90 queue que; 91 92 void init() 93 { 94 while(que.size()) que.pop(); 95 for(int i=0;i