Codeforces Round #635 Kaavi and Magic Spell

链接

考虑S串中第i个字母的贡献，那么我们就可以记录一下前i-1个字母组成的各个区间的个数dp[i] [j] 表示T串的i~j区间匹配 出现的次数，
那么当加入第i个字母时，所有长度为i-1的dp区间答案已经得到，所以我们在T串中直接枚举所有长度为i的区间，即为当前字母的贡献。
转移方程：dp[l][r]+=dp[l+1][r] s[i]==t[l] || l>m
dp[l][r]+=dp[l][r-1] s[i]==t[r] || r>m

难点:两个串长度不相等，初始化，dp[][]数组的意义

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define ls rt<<1
#define rs rt<<1|1
#define pb push_back
#define fi first
#define se second
#define yes puts("YES")
#define no puts("NO")
#define ios ios::sync_with_stdio(0);
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
const int maxn = 1e6 + 6;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
LL qp(LL x,LL y){LL ans=1;x%=mod;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;}
LL inv(LL x){return qp(x,mod-2);}
//head

LL n,m,dp[6030][6030];
char s[maxn],t[maxn];
int main(){
    scanf("%s%s",s+1,t+1);
    n=strlen(s+1);m=strlen(t+1);

    for(int i=1;i<=n+m;i++) dp[i][i-1]=1;

    for(int i=1;i<=n;i++){
        for(int l=1,r=l+i-1;r<=n;l++,r++){
            if(l>m||s[i]==t[l]) (dp[l][r]+=dp[l+1][r])%=mod;
            if(r>m||s[i]==t[r]) (dp[l][r]+=dp[l][r-1])%=mod;
        }
    }
    LL ans=0;
    for(int i=m;i<=n;i++) (ans+=dp[1][i])%=mod;
    printf("%lld\n",ans);
}