历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 1052. 设计密码原题链接中等

作者：

E.lena , 2021-01-01 18:51:23 , 所有人可见 , 阅读 7393

214

66

思路

1.状态机

动态规划

QQ浏览器截图20210101073445.png
为什么这样的状态表示是可行的呢?
因为S数组中的第n位有26个小写字母,匹配在T中的位置一定存在(因为不匹配,匹配到的位置是0),
所以把所有f[n][0~m-1]加起来即为总方案数

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

using namespace std;

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

int f[N][N],ne[N];
char str[N];//子串

int main()
{
    int n,m;
    cin>>n>>str+1;
    m=strlen(str+1);

    for(int i=2,j=0;i<=m;i++)//求出ne数组(kmp模板)
    {
        while(j&&str[j+1]!=str[i]) j=ne[j];
        if(str[j+1]==str[i]) j++;
        ne[i]=j;
    }

    f[0][0]=1;//已经匹配了0位,且匹配的子串的位置是0时的方案数为1;(初始化)
    for(int i=0;i<n;i++)//枚举密码位
     for(int j=0;j<m;j++)//把第i位密码匹配到的子串位置都枚举一遍
     //j表示第i位密码匹配到的位置,因为不能包含子串,所以不能匹配到m这个位置
      for(char k='a';k<='z';k++)//把第i+1所有可能的字母都枚举一遍
       {
           //匹配过程:寻找当第i+1的位置是k时,并且密码已经生成了第i位,匹配的子串的位置是j时,能跳到哪个位置
           int u=j;
           while(u&&str[u+1]!=k) u=ne[u];
           if(str[u+1]==k) u++;

           if(u<m) f[i+1][u]=(f[i+1][u]+f[i][j])%mod;
           //因为是从f[i][j](i+1的位置为k)跳到f[i+1][u]这个位置,所以f[i+1][u]=f[i+1][u]+f[i][j];
           /*
           注:可能存在重边,因为j不同但ne[j]是相同的,并且k是相同的,所以此时
           f[i][j1]和f[i][j2]跳到的位置是一样的(k相同,ne[j1]=ne[j2])
           */
       }

    int res=0;
    for(int i=0;i<m;i++) res=(res+f[n][i])%mod;
    //将所有的方案数加起来即为总方案数
    printf("%d",res);

    return 0;
}

39 评论

yanli 2022-03-20 17:36

K 总说过不偷懒的话，可以预处理出所有的 26 * m * n 种情况，有人试过吗

I_can_do_wonders 2022-04-19 21:19

K总？？

菜菜-胶胶 2022-07-13 12:38

你个假粉丝，明明是J总

RwChen 2022-11-10 10:28 回复了菜菜-胶胶的评论

明明是A总

不好好好 2022-11-29 10:44 回复了 RwChen 的评论

不是X总？

JY_ZKY 2023-01-19 12:48 回复了不好好好的评论

明明是Orz总（恼）

lantano 2023-02-08 19:50

const int N=55;
int jump[N][26];
int ne[N];
char str[N];
int n,m;
int f[N][N];
int mod=1e9+7;
int main()
{
cin>>n>>(str+1);
m=strlen(str+1);
for(int i=2,j=0;i<=m;i)
{
while(j&&str[i]!=str[j+1])j=ne[j];
if(str[j+1]==str[i])j;
ne[i]=j;
}
for(int i=0;i<=m;i)
{
for(char j=’a’;j<=’z’;j)
{
int u=i;
while(u&&j!=str[u+1])u=ne[u];
if(str[u+1]==j)u;
jump[i][j-‘a’]=u;
}
}
f[0][0]=1;
for(int i=0;i<n;i)
{
for(int j=0;j<m;j)
{
for(int k=0;k<26;k)
{
int u=jump[j][k];
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;
}

Deepsea 2023-08-23 15:36

跟优化kmp的ne数组一样，直接指向目标的匹配节点，y总ac自动机有讲

knya 2023-08-23 16:43 回复了 JY_ZKY 的评论

明明是B总

lkr-Carey 11个月前回复了 JY_ZKY 的评论

ennnnn…
正确答案是YXC总

zxh2024 10个月前回复了 lkr-Carey 的评论

不是D总吗?(* ￣︿￣)

无所谓 2023-09-22 13:15

我有一个问题，如果i<j的话怎么匹配呢？不要求j<=i么？？

50_6 4个月前

有佬知道为啥后面j是从0开始吗，j=0、不是没有存字符吗

那年十八打铁如蒟蒻从此结下AK梦 1个月前

0表示压根匹配不上的情况

雾里看花. 2022-08-26 15:20

大佬tql，一直没搞明白 j 为什么取不到 m，看了你的题解豁然开朗啊，orz！！！

Moonbeam_ 2022-07-19 17:04

大佬，能问一下这里的数量是不是状态数量相加

南岸以南南岸哀 2022-07-18 15:28

np，终于知道为啥要加上回退的方案了

瞳星结 2022-04-23 23:38

清晰易懂，thx

天郁闷 2022-03-25 21:34

n刷理解了

knya 2023-08-23 16:44

所以n等于多少

乐天知命故不忧 2022-03-22 21:54

好好准备高考，加油

kuan525 2022-03-12 03:47

请教一下大佬，上面说是有重边的情况我能理解（多个点指向一个点），但是要是一个点可以向前跳到多个点呢，这种情况不用更新所有吗，例如给一个例子abcabcabcddd，前面有三个abc，在遍历到第三个abc的时候为什么只跳到第二个abc而不更新第一个abc呢，求解

shark_big 2022-02-13 21:00

请问要是循环中的f[i+1][u]改为f[i][u]那转移方程怎么写呢（大雾），请高手帮帮我这个大蒟蒻。

瞳星结 2022-04-24 00:18

int main(){
    cin >> n >> str;
    int m = strlen(str);

    for(int i = 0, j = 1; j < n; j++){
        while(i && str[i] != str[j]) i = ne[i - 1];
        if(str[i] == str[j]) ++i;
        ne[j] = i;
    }

    dp[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < m; j++)
            for(int k = 'a'; k <= 'z'; k++){
                int u = j;
                while(u && k != str[u]) u = ne[u - 1];
                if(k == str[u]) ++u;
                if(u < m) dp[i][u] = (dp[i][u] + dp[i - 1][j]) % mod;
            }

    int ans = 0;
    for(int i = 0; i < m; i++)  ans = (ans + dp[n][i]) % mod;
    cout << ans;
}

南岸以南南岸哀 2022-07-18 15:27 回复了瞳星结的评论

u+1和u感觉都是kmp的定义决定而已匹配的模式串和主串得问题

糖豆 2023-05-22 16:20 回复了南岸以南南岸哀的评论

没那么神奇，可以一直过掉的

#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);
    int m = strlen(p + 1);

    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;

    for (int i = 1; i <= n; i++)
        for (int j = 0; j < m && j < i; j++)
            for (char ch = 'a'; ch <= 'z'; ch++) {
                int u = j;
                while (u && ch != p[u + 1]) u = ne[u];
                if (ch == p[u + 1]) u++;
                f[i][u] = (f[i][u] + f[i - 1][j]) % MOD;
            }

    for (int i = 0; i < m; i++) res = (res + f[n][i]) % MOD;

    printf("%d\n", res);
    return 0;
}