题解 P3426 【[POI2005]SZA-Template】

由题意可知这个模式串$p$（印章）一定是主串的公共前后缀之一。 一个暴力的想法就是枚举不同的公共前后缀然后做kmp，判断每次完全匹配的位置之差是否大于其长度，就是说要完全覆盖不能有露出的地方。 然后优化可以采用dp的思想。这个不太好想，我们利用$dp[i]$代表到以字符$s[i]$结尾的前缀的最短印章长度。然后考虑怎么转移。 首先说对于一些情况，比如最长公共前后缀为0（$nxt[i] = 0$）的情况，那么只能让$dp[i]=i$才能全部覆盖。 对于别的情况，我们根据开始所说的性质，这个模式串$p$一定是主串的公共前后缀之一，所以我们感觉应该是与$dp[nxt[i]]$有关，其实当满足某种条件下， $dp[i]=dp[nxt[i]]$是成立的。接下来来说明这一点。 我们知道答案肯定是属于所有的公共前后缀里面的，也就是说答案的集合的范围可以确定了，如果我们考虑另一点$j$，那么$dp[j]$，那么虽然$dp[j]$可能是答案，但是它并不符合我们上面所说的，因为以$j$为结尾的公共前后缀集合和以$i$结尾的公共前后缀集合未必相同。 那么对于$nxt[i]$这一点来说呢，很明显他的所有公共前后缀是包含在$i$中的，也就是$ans(dp[nxt[i]])\in ans(dp[i])$,但是这样还不完备，就是缺少了$nxt[i]$本身，因为$nxt[i]$的公共前后缀是不包括他自己的，如果观察我们的$dp$的转移过程，我们发现$dp[nxt[i]]$的答案集合也是包含了$nxt[i]$自身的，这样就完备了，也就是说**$dp[i]$答案的集合是与$dp[nxt[i]]$一致的**。 那么转移关系就明显了。即 $dp[i] = i\ or \ dp[i] = dp[nxt[i]]$。 什么时候可以转移呢？ 假定我们以$dp[nxt[i]]$作为印章长度，那么我们毫无疑问可以用其覆盖最后的一部分（因为印章也是后缀），但是我们需要知道在前面是否存在一个点$j$，使得到$j$点是可以被$dp[nxt[i]]$所代表的印章覆盖的并且能与最后我们要覆盖的后缀部分衔接上。画个图就清楚了。  在上面的那种情况里绿色的部分是无法被覆盖到的。 所以我们还需要维护不同子串所能覆盖的最后位置，用一个桶来维护。 代码和最上面的题解差不多，就不贴了。