[状态机dp] 设计密码(KMP+状态机模型)

文章目录

0. 前言

相关：

• [kmp+模板] kmp模板

1. KMP+状态机模型

1052. 设计密码

真滴难，后面还有 trie+kmp 搞出来的 AC 自动机，树上 kmp…

思路：

• 本题要求一个长度 N 的密码，那么从 1~N 每个位置都有 26 种字母可能出现的情况，没有限制三的话，那么整个方案数就是 $26^N$ 个
• 简单回顾 KMP 算法：
  • 指针 j，匹配时 S[i]=T[j+1]，j 往前加。失配时 j = ne[j] 往回退。那么当 j 跳到了 T 的末尾，则说明匹配，则当前 S 密码包含了子串 T，即不为合法方案
  • 假设 T 子串长度为 m，则可将 0~m 这 m+1 位置视为状态机的 m+1 个状态
  • 每个状态跳的时候有多少种情况呢？判断 S[i]=T[j+1] 是否成立，成立则 j=j+1，不成立则 j=ne[j]，那么 j 最终跳到哪里完全取决于 S[i] 的取法，即 26 种情况 ，导致了 j 的 26 种可能的跳法。实际上就只能 j=j+1 一种，其它的都是 j=ne[j]。故可以建立一个 $(m+1)\times 26$ 的状态机。每一个 j 位置都对应 26 种情况，会决定它跳向那个位置，然后到了下一个位置，又是 26 种情况，决定它的下下个位置…一直这样匹配完整个 S，如果 j 没有跳到过 m 这个末尾状态的话，说明没匹配，就说明这个 S 是一个合法答案
  • 再进一步抽象为： 在 $(m+1)\times 26$ 的状态机上走 n 步，不走到末尾状态的所有不同的方案数。一个合法方案就唯一对应一个合法路线，一个合法路线就唯一对应一个合法方案
• 时间复杂度： $O(26n^3)$
  • 枚举 n 密码长度 $O(n)$
  • 枚举 j 的位置 $O(n)$
  • 枚举所有字母 $O(26)$
  • 进行 kmp，while 循环 $O(n)$
  • 总的时间复杂度 $O(26n^3)$
• 状态定义：
  • f[i][j]：写到密码串前 i 个字母，且当前跳到 kmp 的第 j 个状态的方案数量
• 状态转移方程： f[i + 1][u] = f[i + 1][u] + f[i][j]。这里的状态定义是已经有的长度，不包括当前枚举的字母。 也可以理解为原来的 f[i][j] = f[i-1][j] 这类的，都是拿后继更新前驱。然而本题是用当前这个后继状态来更新它能到达的所有后继状态。 很不错的思路。

很不错很不错很不错的一道题，花了 2 小时。

代码：

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

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

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

int main() {
    cin >> n >> str + 1;
    
    int len = strlen(str + 1);
    
    // 求next数组
    for (int i = 2, j = 0; i <= len; ++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;            // 状态初始化,一个字母都没有,也是一种方案
    for (int i = 0; i < n; ++i) 
        for (int j = 0; j < len; ++j)               // 枚举j的位置,不包括子串的末尾len
            for (char k = 'a'; k <= 'z'; ++k) {     // i的26种选法,也可视为状态j的26种出边
                int u = j;
                // s[i]失配跳ne,得到最后的kmp位置,在这不论是单个字母还是字符串,kmp都是while,
                // 在此是一个字母就只判断一次,最终停下来u大多都是0吧
                while (u && k != str[u + 1]) u = ne[u];    
                if (k == str[u + 1]) u ++;
                if (u < len) f[i + 1][u] = (f[i + 1][u] + f[i][j]) % MOD;   // 采用后继更新前驱节点
            }
    
    int res = 0;
    for (int i = 0; i < len; ++i) res = (res + f[n][i]) % MOD;
    cout << res << endl;
    
    return 0;
}

2020/11/25
纠结于 kmp 对单个字母的匹配，while。暴露出 kmp 又生疏了的事实…tcl

本文地址：https://blog.csdn.net/yl_puyu/article/details/110135553