欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-20 23:08:45
文章目录0. 前言1. KMP+状态机模型0. 前言相关:[kmp+模板] kmp模板1. KMP+状态机模型1052. 设计密码 真滴难,后面还有 trie+kmp 搞出来的 AC 自动机,树上 kmp…思路:本题要求一个长度 N 的密码,那么从 1~N 每个位置都有 26 种字母可能出现的情况,没有限制三的话,那么整个方案数就是 26N26^N26N 个简单回顾 KMP 算法:指针 j,匹配时 S[i]=T[j+1],j 往前加。失配时 j = ne[j] 往回退。那么当...

0. 前言

相关:

1. KMP+状态机模型

1052. 设计密码

[状态机dp] 设计密码(KMP+状态机模型)
真滴难,后面还有 trie+kmp 搞出来的 AC 自动机,树上 kmp

思路:

  • 本题要求一个长度 N 的密码,那么从 1~N 每个位置都有 26 种字母可能出现的情况,没有限制三的话,那么整个方案数就是 2 6 N 26^N 26N
  • 简单回顾 KMP 算法:
    • 指针 j,匹配时 S[i]=T[j+1]j 往前加。失配时 j = ne[j] 往回退。那么当 j 跳到了 T 的末尾,则说明匹配,则当前 S 密码包含了子串 T,即不为合法方案
    • 假设 T 子串长度为 m,则可将 0~mm+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 ) × 26 (m+1)\times 26 (m+1)×26 的状态机。每一个 j 位置都对应 26 种情况,会决定它跳向那个位置,然后到了下一个位置,又是 26 种情况,决定它的下下个位置…一直这样匹配完整个 S,如果 j 没有跳到过 m 这个末尾状态的话,说明没匹配,就说明这个 S 是一个合法答案
    • 再进一步抽象为: 在 ( m + 1 ) × 26 (m+1)\times 26 (m+1)×26 的状态机上走 n 步,不走到末尾状态的所有不同的方案数。一个合法方案就唯一对应一个合法路线,一个合法路线就唯一对应一个合法方案
  • 时间复杂度: O ( 26 n 3 ) O(26n^3) O(26n3)
    • 枚举 n 密码长度 O ( n ) O(n) O(n)
    • 枚举 j 的位置 O ( n ) O(n) O(n)
    • 枚举所有字母 O ( 26 ) O(26) O(26)
    • 进行 kmpwhile 循环 O ( n ) O(n) O(n)
    • 总的时间复杂度 O ( 26 n 3 ) O(26n^3) O(26n3)
  • 状态定义:
    • 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