修复密码(kmp+状态机dp)

构造的密码位置i和j+1进行匹配，如果i确定，j+1在kmp中的转移是确定的。f[i][j]表示密码构造到i位置，状态是j的方案,枚举i+1位置处放哪个字母，固定后，就可以知道当前状态可以连向哪些状态。dp的复杂度NM26，因为里面现找它的转移到的状态，所以应该再乘M，复杂度为26*N^3

#include<bits/stdc++.h>

using namespace std;

const int N=55,mod=1e9+7;

int n,m;
char str[N];
int f[N][N];

int main()
{
	cin>>n>>str+1;
	m=strlen(str+1);
	
	int ne[N]={0};
	for(int i=2,j=0;i<=m;i++)
	{
		while(j&&str[i]!=str[j+1]) j=ne[j];
		if(str[i]==str[j+1]) j++;
		ne[i]=j;
	}
	
	f[0][0]=1;
	for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			for(char k='a';k<='z';k++)
			{
				int u=j;
				while(u&&str[u+1]!=k) u=ne[u];
				if(str[u+1]==k) u++;
				f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
			}
	
	int res=0;
	for(int i=0;i<m;i++) res=(res+f[n][i])%mod;
	
	cout<<res<<endl;
	
	return 0;
}