点击打开链接
题意：
长度为n的串中，子串没有st串的个数。
题解：
对st串先做一次kmp；
然后再做ss[i][j] 表示前i-1个字符与st串前i-1个相同。而第i个表示j和st串前缀的最大匹配数。
dp[i][j]表示，长度为i的串中 不存在子串st，并且和子串能够匹配的前缀最长为j。
#include <stdio.h> #include <string.h> #include <iostream> #define LL long long using namespace std; const int maxn=1000+100; const int mod=1e9+7; int Next[maxn]; LL dp[maxn][maxn]; int ss[maxn][30]; int n,m; char a[maxn]; void get_Next(char a[]){ Next[1]=0; int j=0,i=1; while(i<=m){ if(j==0||a[i]==a[j]){ Next[++i]=++j; if(a[i]==a[j]) Next[i]=Next[j]; } else j=Next[j]; } for(i=1;i<=m;++i){ for(j=0;j<26;++j){ int ch=j+'a'; int p=i; while(p&&a[p]!=ch) p=Next[p]; ss[i][j]=p; } } } int main(){ while(~scanf("%d %d",&n,&m)){ memset(dp,0,sizeof(dp)); scanf("%s",a+1); get_Next(a); dp[0][0]=1; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) for(int k=0;k<26;++k) dp[i][ss[j][k]]=(dp[i][ss[j][k]]%mod+dp[i-1][j-1]%mod)%mod; int sum=0; for(int i=0;i<m;++i) sum=(sum%mod+dp[n][i]%mod)%mod; printf("%d\n",sum); } return 0; }
