结论题可爱 题意简述 给出一个字符串 ，你可以使用一个印章，每次能印出一个相同的字符串 ，印章印过的地方可以重叠，但是重叠部分的字符必须相同。求最小的印章长度，。 思路分析及证明 首先可以想到 。设 代表恰好覆盖 的长度为 的前缀 所需要的最小的印章长度。 通过尝试，我们容易发现如下引理。 引理0：若 能够恰好覆盖 ， 能够恰好覆盖 ，则 能恰好覆盖 。 证明：...

KMP 可爱的初级字符串算法。是某钻石教练会讲的算法。复杂度线性。 前缀数组（nxt） 定义： 代表 子串 最长的相等的真前缀与真后缀的长度（字符串下标从 开始）。规定 。 可以这样理解： 的意思是将字符串整体向右挪动，当 到达 的位置时，第一次出现前缀与原位置完全吻合。这样，当 位失配时，我们只需要将 挪到 的位置，保证前 位都是正确的，更改第 位。 可...