hdu 3746 Cyclic Nacklace (最小覆盖子串,kmp)

hdu 3746题目链接
题意:给定一个字符串,是一个环(首尾相连),问至少再添加多少个珠子才能使得整个串是循环的。。。

思路:一下子想到了最小覆盖子串的模型。。。我求出最小覆盖子串的长度(n-nxt[n])。然后特判下最小覆盖子串的长度等于字符串长度的情况。。。试着叫了一发。。。竟然就A了[……]

Read more

KMP与最小覆盖子串

参考资料(本文大部分是参考这篇博客,附带一些证明步骤的解释)
首先明确一些概念:
最小覆盖子串:对于某个字符串s,它的最小覆盖子串指的是长度最小的子串p,p满足通过自身的多次连接得到q,最后能够使s成为q的子串。
比如:
对于s=”abcab”,它的最小覆盖子串p=”abc”,因为p通过在它[……]

Read more