$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：已确定\ i\ 位密码，且子串可以匹配到第\ j\ 位的方案$
  $属性：Count$

• $2. 状态转移$
  $密码第\ i\ 位和子串第\ u\ 位可以匹配：f[i+1][u]=(f[i+1][u]+f[i][j])\ \% \bmod$

本题思路： $1.求解\ ne\ 数组 \ \ 2.字符串匹配$

完整代码

#include<bits/stdc++.h>

using namespace std;

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

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

int main()
{
    cin>>n>>str+1;
    m=strlen(str+1);

    //求解 ne 数组
    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; //已确定 0 位密码，且子串可以匹配到第 0 位的方案数
    for(int i=0;i<n;i++) //密码枚举到第 i 位
        for(int j=0;j<m;j++) //枚举第 i 位密码可以匹配的子串
            for(char k='a';k<='z';k++) //枚举密码第 i 位填什么
            {
                int u=j;
                while(u&&k!=str[u+1]) u=ne[u];
                if(k==str[u+1]) u++; //可以匹配
                if(u<m) 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; //已确定 n 位密码，子串不能匹配 m 位的方案数

    cout<<res<<endl;

    return 0;
}