AcWing 1052. 设计密码

你现在需要设计一个密码 S，S 需要满足：

S 的长度是 N；
S 只包含小写英文字母；
S 不包含子串 T；
例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。

请问共有多少种不同的密码满足要求？

由于答案会非常大，请输出答案模 109+7 的余数。

输入格式
第一行输入整数N，表示密码的长度。

第二行输入字符串T，T中只包含小写字母。

输出格式
输出一个正整数，表示总方案数模 109+7 后的结果。

数据范围
1≤N≤50,
1≤|T|≤N，|T|是T的长度。

输入样例1：
2
a
输出样例1：
625
输入样例2：
4
cbc
输出样例2：
456924

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N=55,mod = 1e9 + 7;
int f[N][N];//表示考虑总mm前i个字符 不包含字符的前j个字符
int ne[N];
int n,m;
char s[N];

int main()
{
    cin>>n;
    cin>>s+1;

    m=strlen(s+1);//不包括第一个字符

    //预处理不包含字符串的kmp
    for(int i=2,j=0;i<=m;i++)
    {
        while(j && s[j+1] != s[i]) j=ne[j];
        if( s[j+1] == s[i]) j++;
        ne[i]=j;
    }

    //初始化
    f[0][0]=1;

    //mm总位数为n
    for(int i=0;i<n;i++)
    {
        //考虑不包含字符 一共m+1个状态 但是不能走到最后一个（m)位置
        for(int j=0;j<m;j++)
        {
            //枚举第j位能不能放某字符
            for(char k='a';k<='z';k++)
            {
                int u=j;
                while( u && s[u+1] != k ) u=ne[u];
                if( s[u+1] == k ) u++;
                if( u < m )
                    f[i+1][u]=(f[i+1][u] + f[i][j]) % mod;
            }
        }
    }

    int res=0;
    //答案是总方案数的mod和
    for(int i=0;i<m;i++) res=(res+f[n][i]) % mod;

    cout<<res<<endl;

    return 0;
}