题目描述

难度分:$2200$

输入长度不超过$3000$的字符串$S$，只包含小写字母。设$S$的长度为$n$。

输入长度不超过$n$的字符串$T$，只包含小写字母。

从一个空字符串$A$开始，执行如下操作不超过$n$次：

• 删除$S$的第一个字母，然后加到$A$的开头或者末尾。

问：要使$T$是$A$的前缀，有多少种不同的操作方式？模$998244353$。

注：即使两个不同的操作方式得到了相同的字符串$A$，也算不同的操作方式。

输入样例$1$

abab
ba

输出样例$1$

12

输入样例$2$

defineintlonglong
signedmain

输出样例$2$

0

输入样例$3$

rotator
rotator

输出样例$3$

4

输入样例$4$

cacdcdbbbb
bdcaccdbbb

输出样例$4$

24

算法

动态规划

这个题主要的难度就在于状态的设计，设原串$s$的长度为$n$，$t$的长度为$m$。

状态定义

$f[l][r]$表示用$s$前$r-l+1$个字符拼出$t[l…r]$的方案数，由于新串$A$的长度$len$最多就是$n$（原串$s$的长度），所以答案应该就是$\Sigma_{len=m}^{n}f[1][len]$

状态转移

$base$ $case$：用$s$的第一个字符得到$t[i]$的方案数，当$s[1]=t[i]$且$i \gt m$时，$f[i][i]=2$（可以头插也可以尾插，所以有两种方案）。

一般情况：当要用长度为$len$的$s$前缀构造$t[l…r]$时，需要满足$l \in [1,n+1-len]$。假设头插，就需要满足$s[len]=t[l]$或$l \geq m$，此时就是在$t[l+1…r]$上转移过来的，状态转移方程为$f[l][r]=f[l+1][r]$；假设尾插，就需要满足$s[len]=t[r]$或$r \geq m$，此时是在$t[l…r-1]$上转移过来的，状态转移方程为$f[l][r]=f[l][r-1]$。并且两种情况可能都存在，那状态转移方程就是$f[l][r]=f[l+1][r]+f[l][r-1]$。

复杂度分析

时间复杂度

枚举长度时间复杂度$O(n)$，枚举左端点$l$时间复杂度$O(n)$。单次状态转移是$O(1)$的，所以算法整体的时间复杂度为$O(n^2)$。

空间复杂度

空间瓶颈在于DP数组$f$，它是$n^2$级别的，因此算法额外空间复杂度为$O(n^2)$。

C++ 代码

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

using namespace std;

const int N = 3010, MOD = 998244353;
int n, m, f[N][N];
char s[N], t[N];

int main() {
    scanf("%s", s + 1);
    scanf("%s", t + 1);
    n = strlen(s + 1);
    m = strlen(t + 1);
    memset(f, 0, sizeof f);
    for(int i = 1; i <= n; i++) {
        f[i][i] = ((m < i || s[1] == t[i])? 1: 0)<<1;
    }
    for(int len = 2; len <= n; len++) {
        for(int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            if(m < l || s[len] == t[l]) {
                f[l][r] = (f[l][r] + f[l + 1][r]) % MOD;     // 放前面
            }
            if(m < r || s[len] == t[r]) {
                f[l][r] = (f[l][r] + f[l][r - 1]) % MOD;     // 放后面
            }
        }
    }
    int ans = 0;
    for(int len = m; len <= n; len++) {
        ans = (ans + f[1][len]) % MOD;
    }
    printf("%d\n", ans);
    return 0;
}