python/TangDou/AcWing/Statemachine/1052.md

##AcWing 1052. 设计密码

一、题目描述

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

• S 的长度是 N
• S 只包含小写英文字母(a~z)
• S 不包含子串 T

例如：abc 和 abcde 是 abcde 的子串，abd 不是 abcde 的子串。

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

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

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

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

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

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

输入样例1：

2
a

输出样例1：

625

输入样例2：

4
cbc

输出样例2：

456924

二、题目分析

① len=strlen(p+1) ，即len是模式串的长度

scanf("%s", a + 1);      //输入abcdef，共6个字符,放过下标为0的位置，从下标为1开始
int len = strlen(a + 1); //含义：从a下标偏移为1开始，计算到末尾\0的长度
printf("%d", len);       //输出答案：6,理解：让从1开始，到末尾，尾巴在哪里自己找，计算返回长度

② 模式串是固定的，但s串是动态随便生成的,s串中的每个位置上都有a \sim z共26种可能

闫氏DP分析法

预求 所有长度为n的生面的密码字符串中，不出现子串 p 的方案数

状态表示

• 集合 f[i][j]:密码已生成i位，并且，第i位匹配到子串p的位置是j的所有方案
• 属性 count(方案数)

状态转移 \large f[i][j]：已经成功构建了一个长度为i的密码，当前密码串与模式串的匹配位置是j的情况

思考它的下一步变化：

• ① 下一步枚举尝试的字符，与p串的p[j+1]相等，并且，需要满足p串的j+1<m,也就是不能完整匹配成功。 \large f[i+1][j+1]+=f[i][j] \ (j+1<m) (i,j)状态的方案数可以累加到(i+1,j+1)状态的方案数上去

• ②下一步枚举尝试的字符，与p串的p[j+1]不等，那么当前 状态匹配 会去往何方呢？根据kmp知识，就是 目标 密码已经生成了i+1位，并且，第i+1位匹配到子串的位置是x时的方案数 ！那这个x是什么东西呢？就是 失配时的跳转位置。

Q:为啥这么做对呢？ 你想啊，现在要构造的密码串，是不是得避开模式串p,也就是不允许密码串中出现模式串p,换言之，见到模式串p就不允许选择，那你怎么能快速知道一个长串中是不是包含了某个子串p呢？当然是用kmp啊！

时刻保持警惕心，怕碰到红线，不允许出现p串，不就是随时需要记录准备好现在与p串匹配了多少吗，这个都不记录，你知道下面会不会出现p串？当然不能啦。

初始值 f[0][0]=1

结果 \displaystyle res=f[n][0]+f[n][1]+f[n][2]+....+f[n][m-1]=\sum_{j=0}^{m-1}f[n][j] s串必须有n个长度，但p串不允许匹配到m,最多只能到m-1,到了m的话，就是完整匹配，也就是s串包含了p串。

四、Code

#include <bits/stdc++.h>
using namespace std;

const int N = 55;
const int MOD = 1e9 + 7;

int n, ne[N];
int f[N][N];
char p[N];
int res;

int main() {
    scanf("%d %s", &n, p + 1); // 读入模式串,存入到p数组中，下标从1开始
    int m = strlen(p + 1);     // 模式串的长度,读到\0结束，会自动计算出p串的长度

    // kmp利用模式串求ne数组【模板】
    for (int i = 2, j = 0; i <= m; i++) {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    f[0][0] = 1; // 递推起点,文本串0个字符，模板串0个字符，此时，方案数是1，其它状态都是0种方案

    // 开始填充dp表,为什么i,j都要从0开始呢？这其实要先看一下状态转移方程f[i][j]出现在了方程中，而初始值是边界
    // f[0][0]=1,所以填表的时候，自然也就是从i=0,j=0开始才能使用上初始值
    for (int i = 0; i < n; i++)                        // 阶段
        for (int j = 0; j < m && j <= i; j++)          // 匹配长度,需要注意的是完成一个字符ch的匹配，则j++,所以，j的上限是m-1,以达到f[n][m]的最终状态
            for (char ch = 'a'; ch <= 'z'; ch++) {     // 准备填充的下一个字符ch
                int u = j;                             // 要退到哪里去呢？
                while (u && ch != p[u + 1]) u = ne[u]; // 不断回退，找到新起点
                if (ch == p[u + 1]) u++;               // 如果匹配下一个字符
                f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;
            }

    // 枚举源串长度是n, 模式串匹配度不足m的，累加
    for (int i = 0; i < m; i++) res = (res + f[n][i]) % MOD;

    cout << res << endl;
    return 0;
}