【经典】区间dp——cf1336E

感觉还是题做少了，比赛的时候感觉就差那么一点，结果是没有往区间dp这方面去想

/*
首先有个挺重要的性质：s[1..k]的字符一定会挨在一块
再将T扩充成和S长度一样，后面补上通配符
区间dp:dp[l][r]表示T的[l..r]区间被凑出来的方案数
外层枚举长度len

*/
#include<bits/stdc++.h>
using namespace std;
#define N 5005
#define mod 998244353
#define ll long long 
ll dp[N][N],n,m;
char s[N],t[N];
int main(){
    cin>>(s+1)>>(t+1);
    n=strlen(s+1);
    m=strlen(t+1);
    for(int i=m+1;i<=n;i++)t[i]='*';
    
    for(int i=1;i<=n;i++)
        if(t[i]==s[1] || t[i]=='*')
            dp[i][i]=1;
            
    for(int len=2;len<=n;len++){
        for(int l=1;l+len-1<=n;l++){
            int r=l+len-1;
            if(s[len]==t[l] || t[l]=='*')
                dp[l][r]=(dp[l][r]+dp[l+1][r])%mod;
            if(s[len]==t[r] || t[r]=='*')
                dp[l][r]=(dp[l][r]+dp[l][r-1])%mod;
        }
    }
    
    ll ans=0;
    for(int i=m;i<=n;i++)
        ans=(ans+dp[1][i])%mod;
    
    cout<<ans*2%mod<<'
';
}