AcWing 1052 设计密码 DP 状态机

    #include<bits/stdc++.h>
    
    using namespace std;
    
    const int N = 55, mod = 1e9 + 7;
    
    int n, m;
    char str[N];
    int nxt[N];
    int f[N][N];//f[i][j]表示长度为i的字符串，且 
    
    int main()
    {
    	cin>>n>>str + 1;
    	m = strlen(str + 1);
    	
    	for(int i = 2, j = 0; i <= m; i ++ ){
    		while(j && str[i] != str[j + 1]) j = nxt[j];
    		if(str[i] == str[j + 1]) j ++ ;
    		nxt[i] = j;
    	}
    	
    	f[0][0] = 1;//因为空集