标题效果：给定的长度m数字字符串s。求不包括子s长度n数字串的数目

n<=10^9 看这个O(n)它与

我们不认为这 令f[i][j]长度i号码的最后的字符串j位和s前者j数字匹配方案

例如，当s至12312时间 f[i][3]它表示的长度i。123结尾且不包括子串”12312“的方案数

a[x][y]为f[i-1][x]转移至f[i][y]的方案数

换句话说(可能描写叙述不清楚) a[x][y]为s的长度为x的前缀加上一个数字后 后缀能够与最长长度为y的前缀匹配 这个数字能够有多少种

比方说12312 这个数字串生成的a数组为(数组从0開始)：

9 1 0 0 0 0

8 1 1 0 0 0

8 1 0 1 0 0

9 0 0 0 1 0

8 1 0 0 0 1

a[2][1]=1 表示长度为2的前缀加上一个'1'之后最多与长度为1的前缀匹配

a[4][0]=8 表示长度为4的前缀加上'1''2'以外的数就变成了长度为0的前缀

可是a[x][5]表示全然匹配，不满足要求的题意，所以我们矩阵乘法时不考虑这一列

我们发现f[i-1]乘上这个矩阵就变成了f[i] 这个矩阵怎么求呢？KMP算法，对于每一个长度的前缀枚举下一个字符进行转移 详细写法详见代码

f初值是f[0][0]=1,f[0][x]=0 (x>0)

于是最后我们仅仅须要取答案矩阵的第一行就可以

去网上找了一堆题解才看懂0.0 这里写的略微具体一点吧

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;struct matrix{	int xx[22][22];	int* operator [] (int x)	{		return xx[x];	}}a,b;int n,m,p,ans;char s[100];int next[100];void operator *= (matrix &x,matrix &y){	int i,j,k;	matrix z;	memset(&z,0,sizeof z);	for(i=0;i
         
          >=1;	}}int main(){	int i;	cin>>n>>m>>p;	scanf("%s",s+1);	KMP();	for(i=0;i
         
        
       
      
     

版权声明：本文博客原创文章，博客，未经同意，不得转载。