题目
传送门 to luogu
思路
第一个字符会在哪里？真不好找。可能在任何地方。不好判断。
正难则反。最后一个字符在哪里？在末尾，或者在开头。所以进行匹配。
然后思路很明显了。对于最后的字符串 ，每次只会匹配开头、结尾，所以用区间 。 视作通配符即可。
题目中要求，任何长度时都可以进行匹配。显然，对于长度 ，仍然是以 作为结束，所以我们只需要累加之前得到的 值就没了。
代码
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}
template < class T >
void getMax(T&a,T b){ if(a < b) a = b; }
template < class T >
void getMin(T&a,T b){ if(b < a) a = b; }const int MaxN = 3005;
const int Mod = 998244353;
int dp[MaxN][MaxN]; // T的i到j
char s[MaxN], t[MaxN];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 j=0; j<n; ++j)for(int i=1; i+j<=n; ++i){if(m < i || s[j+1] == t[i])dp[i][i+j] += dp[i+1][i+j];if(m < i+j || s[j+1] == t[i+j])dp[i][i+j] += dp[i][i+j-1];dp[i][i+j] %= Mod;}int ans = 0;for(int i=m; i<=n; ++i)ans = (ans+dp[1][i])%Mod;printf("%d\n",ans);return 0;
}