好题:KMP+动态规划:CF808G
传送门:https://vjudge.net/problem/CodeForces-808G
题目大意:给你字符串S,T。字符串S中有问号，可以随意填a ~ z 中任意一个字母。问你如何填使得T在S中出现的次数最多(可以重复匹配)。求这个次数。(S , T <= 1e5, |S| * |T| <= 1e7)
题目思路:
看到|S| * |T| <= 1e7,自然可以想到将这两维放入dp中。即
考虑一个重要的问题：当i,j失配的时候，j如何移动?
注意到题目中说了可以重复匹配，那么j = next[j]。但是 S[i] 不一定就等于 T[next[j]].所以需要暴力跳fail指针，这样的复杂度显然太高，所以我们还需要预处理一个F.
在dp的转移过程中，还要考虑一个很重要的东西: 转移方式为 刷表法 还是 填表法 ？
1.想象一下填表法，也就是对于特定的dp[i][j],我们需要找出它的前导状态。但是前导状态真的好找么？
对于 j , 它从哪里来是很难确定的。因为它是从 某个 pre 的 next[next[...pre]] = j 转移而来的。
2.刷表法，也就是对于特定的dp[i][j],去找它能影响的下一个状态。对于这个问题来说就很明朗了。
因为 j 的下一个状态显然就是 . (不过注意刷表法只适用于每个状态所依赖的状态对它的影响独立).
so,刷表法的套路:
初始化： dp[i][j] = -1 , 边界条件:dp[0][0] = 0.
然后当且仅当 dp[i][j] != -1 时才转移。
当S[i] != '?' 时
否则， 26个字母如上暴力枚举转移即可。
最后答案为：
