题：https://codeforces.com/contest/1337/problem/E
题意：给定长为n的字符串S和长为m的字符串T，有一个空字符串A，对S有俩种操作，1是将S的第一个字符放在A的首部，将S的第一个字符放在A的尾部，问有多少种构造序列能让A的前缀为T
分析：令dp[i][j]为匹配到T字符串[i,j]的方案数，那么答案就是sum（dp[1][x]）（m<=x<=n）；
dp[l][r]由dp[l + 1][r] 和 dp[l][r + 1]转换而来，因为假设我们知道了[l+1,r], [l,r+1]这俩个区间的方案数，对区间[l,r]转移的充分必要条件分别为s[i]==t[l]和s[i]==t[r];
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int M=3333; const int mod= 998244353; ll dp[M][M]; char s[M],t[M]; int main(){ scanf("%s%s",s+1,t+1); int n=strlen(s+1),m=strlen(t+1); for(int i=1;i<=n+1;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],ans%=mod; printf("%lld\n",ans); return 0; }
E - Kaavi and Magic Spell(区间dp)
原文：https://www.cnblogs.com/starve/p/12719212.html
