[Acwing] 1052. 设计密码 状态机模型

前言

传送门 :

感觉这个题不应该分类到状态机里面啊

思路

状态表示 :
f [ i ] [ j ] f[i][j] f[i][j]到第 i i i位,且匹配到 j j j的方案数

状态转移 :
每次通过 K M P KMP KMP的 n e ne ne数组进行转移

Mycode

const int N  = 55 , mod = 1e9+7;
int f[N][N] , ne[N];
//已经生成了i位,并且匹配到了j位
char str[N];

void solve(){
	int n,m;
	cin>>n>>str+1;
	m = strlen(str+1);
	
	
	//用来求ne数组
	for(int i=2,j=0;i