题意：给定你m个模式串，问你长度小于等于L的符串中，有多少包含着这些模式串。
思路：这个题的思路求解类似于POJ2778，只不过那一题求未包含模式串，而这一题求的是包含模式串的数量，可构造字符串的总数量减去不包含模式串的字符串数量，就可以得到包含模式串的数量。 但还有一个问题就是L < 2^31,规模太大 肯定不能直接求解小于等于L的字符串的数量。 由此可得这个问题便可以用矩阵快速幂求解来完成，因此这个题目就是AC自动build一下，再加上矩阵快速幂的构造来完成的，很类似与poj2778，注意问题也和上一题相似
AC代码：
#include <bits/stdc++.h> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <queue> #include <iostream> // 和前面一题 差不多 在另外加上一个 矩阵快速幂的求解过程 // 求一个很大的序列的时候 可以尝试用矩阵写出来 看前后项之间的关系 从而 推得 能否用矩阵快速幂的方法求解 using namespace std; typedef unsigned long long ull; const int MAX_tot = 37; const int MAXN = 17; struct Matrix { ull mat[MAX_tot][MAX_tot]; int n; Matrix(){} Matrix(int num){ n = num; for(int i = 0;i < n;i ++){ for(int j = 0;j < n;j ++) mat[i][j] = 0; } } }; Matrix mul(Matrix a,Matrix b) { Matrix tmp = Matrix(a.n); for(int i = 0;i < a.n;i ++){ for(int j = 0;j < a.n;j ++){ for(int k = 0;k < a.n;k ++){ ull sum = a.mat[i][k] * b.mat[k][j]; tmp.mat[i][j] = tmp.mat[i][j] + sum; } } } return tmp; } Matrix quickpow(Matrix a,int n) { Matrix E = Matrix(a.n); for(int i = 0;i < a.n;i ++) E.mat[i][i] = 1;//单位矩阵 while(n){ if(n&1) E = mul(E,a); a = mul(a,a); n >>= 1; } return E; } struct Aca { int size,Next[MAX_tot][26],fail[MAX_tot],end[MAX_tot]; queue<int>q; void init() { while(!q.empty()) q.pop(); for(int i = 0;i < MAX_tot;i ++){ fail[i] = end[i]= 0; for(int c = 0;c < 26;c ++) Next[i][c] = 0; } size = 1; } void insert(char *s) { int len = strlen(s),p = 1; for(int i = 0;i < len;i ++){ int ch = s[i] - 'a'; if(!Next[p][ch]) Next[p][ch] = ++size; p = Next[p][ch]; } end[p] = 1; } void build() { for(int i = 0;i < 26;i ++) Next[0][i] = 1; q.push(1); fail[1] = 0; while(!q.empty()){ int p = q.front(); q.pop(); for(int i = 0;i < 26;i ++){ int now = Next[p][i]; int fafail = fail[p]; if(!now){ Next[p][i] = Next[fafail][i]; continue; } fail[now] = Next[fafail][i]; q.push(now); } end[p] |= end[fail[p]];//利用父节点 更新当前节点的信息 } } Matrix getmatrix() { Matrix tmp = Matrix(size+1); for(int i = 1;i <= size;i ++){ for(int j = 0;j < 26;j ++){ if(end[Next[i][j]]) continue; tmp.mat[i-1][Next[i][j]-1]++; } } for(int i = 1;i <= size+1;i ++) tmp.mat[i-1][size] = 1; return tmp; } }aca; void opMatrix(Matrix a) { for(int i = 0;i < a.n;i ++){ for(int j = 0;j < a.n;j ++){ printf(j == a.n-1?"%d\n":"%d ",a.mat[i][j]); } } } char s[MAXN]; int main() { int n,l; while(~scanf("%d%d",&n,&l)){ aca.init(); for(int i = 1;i <= n;i ++){ scanf("%s",s); aca.insert(s); } aca.build(); Matrix A = aca.getmatrix(); //opMatrix(A); ull res = 0; A = quickpow(A,l); //opMatrix(A); for(int i = 0;i < A.n;i ++){ res += A.mat[0][i]; } res--; //printf("%d\n",res); //opMatrix(ansA); Matrix T = Matrix(2); T.mat[0][0] = 26,T.mat[0][1] = 1,T.mat[1][1] = 1; T = quickpow(T,l); ull ans = T.mat[0][0] + T.mat[0][1]; ans--; ans -= res; cout<<ans<<endl; } return 0; }