Solution. CF1336C Kaavi and Magic Spell

Description

给定一个字符串 $S$ 和一个字符串 $T$，每次操作可以删掉 $S$ 的第一个字符，然后放到一个初始为空的字符串 $A$ 的首部或尾部，你可以进行任意次操作，求有多少种不同的方法使得 $T$ 是 $A$ 的前缀。

$|T|\le|S|\le3000$

Solution

先考虑 $|S|=|T|$ 的情况。

设 $f_{i,j}$ 表示用 $S$ 的前 $j-i+1$ 位构造出 $T_{i\dots j}$ 的方案数。

不难得到转移方程：
$$
f_{i,j}=[S_{j-i+1}=T_i]f_{i+1,j}+[S_{j-i+1}=T_j]f_{i,j-1}
$$
初始化：
$$
f_{i,i}=[S_1=T_i]2
$$
区间 dp 即可。

如果 $|S|>|T|$，那么对于最后构造出来的 $A$，$(|T|,|A|]$ 这些位是什么我们并不关心，也就是说，我们实际上可以将 $T$ 的长度补至与 $S$ 等长，补充的这些位能够与任意字符匹配。

答案即为 $\sum_{i=|T|}^{|S|}f_{1,i}$。

Code

namespace Main{
    const int MOD = 998244353;
    const int L = 3005;
    int ls, lt, ans, f[L][L];
    char s[L], t[L];
    void Main(){
        scanf("%s%s", s + 1, t + 1);
        ls = strlen(s + 1), lt = strlen(t + 1);
        for(ri i = 1; i <= lt; i++) if(s[1] == t[i]) f[i][i] = 2;
        for(ri i = lt + 1; i <= ls; i++) f[i][i] = 2;
        for(ri len = 2; len <= ls; len++){
            for(ri i = 1; i + len - 1 <= ls; i++){
                ri j = i + len - 1;
                if(i > lt || s[len] == t[i]) f[i][j] += f[i+1][j];
                if(j > lt || s[len] == t[j]) f[i][j] += f[i][j-1];
                f[i][j] %= MOD;
            }
        }
        for(ri i = lt; i <= ls; i++) ans = (ans + f[1][i]) % MOD;
        write(ans);
        return;
    }
} // namespace

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。