1. 题目

给出一个长度为$m$的字符串(由0~9构成)

求不包含该子串(连续子串)的长度为$n$的字符串个数(由0~9构成),答案对$k$取模。

$n\leq 10^3,M\leq 20,k\leq 1000$

2. 题解

谢谢ABS同学教我这题啦~

先对给出的字符串跑一遍Kmp求出其next数组。

然后设$f[i,j]$已经构造的字符串(长度为$i-1$)的后缀与模式串的前缀的最长公共长度为$j$时,构造$[i, n]$的方案数。

对于$f[i,j]$枚举第$i$个字符,若与模式串的第$j+1$个字符相同则从$f[i+1,j+1]$转移状态,否则说明失配,从$f[i+1,nxt[…]]$转移状态。这里的$nxt[…]$指的是nxt一直根据模式串的nxt数组跳,直到跳到某个位置,比如是$nxt[x]$,使得模式串的$nxt[x]+1$个字符与当前枚举的字符相同。也有可能一直失配,那么$nxt[…]$就是0了。这个和Kmp匹配字符串是相同的。

这样复杂度是$O(n^3)$的。

其实还可以与处理一下$pre[i,c]$表示当前匹配了$i$个,然后当前要填$c$,会跳到哪里去。这个预处理是$O(n^2)$的,然后再跑Dp也是$O(n^2)$的了。

代码($O(n^3)$):

#include <bits/stdc++.h>

#define NS (1005)

using namespace std;

int n, m, k, nxt[NS], f[NS][NS];

char str[NS];

void Kmp()
{
    for (int i = 2, j = 0; i <= m; i += 1)
    {
        while (j && str[j + 1] != str[i]) j = nxt[j];
        if (str[j + 1] == str[i]) j++;
        nxt[i] = j;
    }
}

int Dp(int a, int b)
{
    if (b == m) return 0;
    if (a > n) return 1;
    if (f[a][b] != -1) return f[a][b];
    int& F = f[a][b]; F = 0;
    for (char c = '0'; c <= '9'; c += 1)
    {
        if (c == str[b + 1]) F += Dp(a + 1, b + 1);
        else
        {
            int j = nxt[b];
            while (j && c != str[j + 1]) j = nxt[j];
            if (c == str[j + 1]) j++;
            F += Dp(a + 1, j);
        }
        F %= k;
    }
    return F;
}

int main(int argc, char const* argv[])
{
    scanf("%d%d%d%s", &n, &m, &k, str + 1), memset(f, -1, sizeof(f));
    Kmp(), printf("%d\n", Dp(1, 0));
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *