AcWing 1052. 设计密码

题目传送门

一、思路

• 状态机
  

• 动态规划
  

• 问题
  为什么这样的状态表示是可行的呢?
  因为\(S\)数组中的第\(n\)位有\(26\)个小写字母,匹配在\(T\)中的位置一定存在(因为不匹配,匹配到的位置是\(0\)),所以把所有\(f[n][0 \sim m-1]\)加起来即为总方案数。

二、原始版本

#include 

using namespace std;
const int N = 55;
const int mod = 1e9 + 7;

int n;          //n个长度的密码串
int m;          //模板串的长度
int ne[N];      //kmp的ne数组
char p[N];      //模板串
int f[N][N];    //f[i][j]表示密码已经生成了i位，并且第i位匹配到模板串中位置为j时的方案数,这是方案数互相依赖相加的准确依据

int main() {
    //构建的密码长度n
    cin >> n >> (p + 1);//模板串p,模板串的下标是从1开始的
    //计算模板串s的字符串长度
    m = strlen(p + 1);

    //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;
    }

    //已经匹配了0位,且匹配的子串的位置是0时的方案数为1;(初始化)
    f[0][0] = 1;

    for (int i = 0; i < n; i++)//枚举密码串的每一位,这是一个DP打表的过程，所以从小到大遍历每一位
        for (int j = 0; j < m; j++)//根据状态定义，需要枚举的第二维就是模板串的每一个位置
            //j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置
            //认为前面i,j已经完成匹配的情况下，讨论密码串第i+1位的26种可能
            for (char k = 'a'; k <= 'z'; k++) {
                //在s[i+1]=k的时候，模板串需要跳到哪个位置?
                int u = j;
                while (u && k != p[u + 1]) u = ne[u];
                if (k == p[u + 1]) u++;
                //[i+1,u]这个状态是可以被[i,j]转化而来的
                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;
    //将所有的方案数加起来即为总方案数
    printf("%d", res);
    return 0;
}

优化一维复杂度降低到n^2
将建图部分抽取出来即可。。。！
时间复杂度：O(26n2)

三、优化版本

#include 

using namespace std;

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

int n;          //n个长度的密码串
int m;          //模板串的长度
int ne[N];      //kmp的ne数组
char p[N];      //模板串
int f[N][N];    //f[i][j]表示密码已经生成了i位，并且第i位匹配到模板串中位置为j时的方案数,这是方案数互相依赖相加的准确依据
int g[N][26];   //


int main() {
    //构建的密码长度n
    cin >> n >> (p + 1);//模板串p,模板串的下标是从1开始的
    //计算模板串s的字符串长度
    m = strlen(p + 1);

    //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;
    }

    // 预处理(可以优化一下，有重复的不用重新计算)
    for (int j = 0; j < m; j++)
        for (int k = 'a'; k <= 'z'; k++) {
            int u = j;
            while (u && p[u + 1] != k) u = ne[u];
            if (p[u + 1] == k) u++;
            //记录下这个数据
            g[j][k - 'a'] = u;
        }
    // 状态计算
    f[0][0] = 1;
    for (int i = 0; i < n; i++)//枚举密码串的每一位,这是一个DP打表的过程，所以从小到大遍历每一位
        for (int j = 0; j <= m; j++)//根据状态定义，需要枚举的第二维就是模板串的每一个位置
            //j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置
            //认为前面i,j已经完成匹配的情况下，讨论密码串第i+1位的26种可能
            for (char k = 'a'; k <= 'z'; k++) {
                //模板串跳到哪个位置?
                //模板串跳到哪个位置，与两个因素有关，1：j现在所在的位置，2：遇到的s[i+1]是什么，即k
                int u = g[j][k - 'a'];
                //状态转移
                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;
    //将所有的方案数加起来即为总方案数
    printf("%d", res);
    return 0;
}