[CF1336C] Kaavi and Magic Spell

Description

给定一个字符串 (S) 和一个字符串 (T)，每次操作可以从 (S) 的开头删去一个字符，把它加到一个初始为空的串的开头或结尾，不必删完，求有多少种不同的方法使得 (T) 是 (A) 的前缀。

Solution

所谓要求 (T) 是 (A) 的前缀，即要求 (A) 的前 (T) 个字符是 (A)。

考虑 dp，设 (f[i][j]) 表示用 (S) 的前 (j-i+1) 个字符构造出 (T[i..j]) 的方案数。

考虑转移，每次若 (T[i]=S[j-i+1])，那么 (f[i][j] leftarrow f[i+1][j])，反过来也同理。

初态条件可以直接令所有 (f[i][i-1]=1)。

最终的答案即为 (sum_{i=|T|}^{|S|} f[1][i])。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 5005;
const int mod = 998244353;

char s[N],t[N];
int f[N][N],n,m;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>s+1>>t+1;
    n=strlen(s+1);
    m=strlen(t+1);

    for(int i=0;i<=n;i++) f[i+1][i]=1;
    for(int len=1;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            if(i>m || t[i]==s[j-i+1]) 
            {
                f[i][j]+=f[i+1][j];
            }
            if(j>m || t[j]==s[j-i+1])
            {
                f[i][j]+=f[i][j-1];
            }
            f[i][j]%=mod;
        }
    }

    // for(int i=1;i<=n;i++)
    // {
    //     for(int j=1;j<=i;j++) cout<<f[j][i]<<"	";
    //     cout<<endl;
    // }

    int ans=0;
    for(int i=m;i<=n;i++) 
    {
        ans+=f[1][i];
        ans%=mod;
    }

    cout<<ans<<endl;
}