KMP+状态转移

标签：状态 小写字母 密码 int 55 KMP 转移

题目:

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

1. S的长度是 N；
2. S只包含小写英文字母；
3. S不包含子串 T；

请问共有多少种不同的密码满足要求？
由于答案会非常大，请输出答案模 1e9+7的余数。

输入格式：
第一行输入整数N，表示密码的长度。
第二行输入字符串T，T中只包含小写字母。

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

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

分析:

关于是否包含子串的问题，可以使用kmp来尝试实现，另外此题涉及状态的转移，我们定义f[i][j]为密码设计到第i位时，T匹配到了第j位时的方案数，那么下一个状态f[i+1][t],t为通过kmp转移到的下一个的状态（T的下标），另外由于转移得到的状态与密码i+1位的小写字母是什么有关，我们可以通过枚举26个小写字母，计算出所有转移后可能的状态，一个状态可能有多个不同的状态转移得到，因为求的是方案数，我们需要累加，所以得到状态转移方程位f[i+1][t] += f[i][j]。

最终的答案是max(f[n][0~m-1]),m为不包含的子串的长度.

代码:

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

int mod = 1e9 + 7;
int n;
char s[55];
int ne[55];
int f[55][55];

int main(){
    cin >> n >> s + 1;
    int m = strlen(s + 1);
    //求出ne数组，用于状态转移
    for(int i = 2, j = 0; i <= m; i ++){
        while(j && s[i] != s[j + 1]) j = ne[j];
        if(s[i] == s[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 ++){
                //枚举每一个先前状态j和i位为k时，累加到转移后的状态。
                int u = j;
                while(u && k != s[u + 1])u = ne[u];
                if(k == s[u + 1])u ++;
                //因为密码中不能包含子串T，所以u<m时，才可以转移
                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;
    cout << res;
}

标签：状态,小写字母,密码,int,55,KMP,转移
From： https://www.cnblogs.com/cjwfly/p/18308076