CVBB ACM Team

水题一道

水题一道

这种关于三个数求最小值，可以要先考虑中间那个。

例如本题，枚举中间那一个，然后在另外两个分别找前驱和后继即可。

一般题，想得有点久了。

显然串S不断的填在T中出现的是连续的一段，那我们不妨把T看作一个长度与S相同的串，第m+1到第n位是通配符。

区间的肯定就考虑区间dp，dp[i][j]表示第i位到第j位都匹配好了的方案数，

那么我们就有了dp[i][i]=(i>m || S[1]==T[i])的初始化，

枚举len，

每次往原区间的左边或者右边加一个，如果能匹配上，加上这个dp值即可。

最后答案是$\sum_{i=m}^{n} dp[1][i]$