Yahbim @ 2021-03-28 10:36:43
这里说了原前缀必须是Q+Q的前缀，也就是说Q+Q的长必须比原前缀的长要大;而Q的长实际上是该语句
while(fail[j]) j=fail[j];循环到底后的（i-j)的长,如何保证其两倍一定比原前缀长要大？
by wjd_ @ 2021-07-07 21:14:19
可证明使得与s前后缀相等的最小串长度<=n/2，即证明所求串对应s中的前后缀不重叠
假设重叠。
设该串长度为i，分重叠部分与n-i大小比较讨论
重叠部分长度<n-i显然存在一个长度更小的串，矛盾
重叠部分长度>n-i时可证串形如"abcabcab"，能找到形如"ab"这个更短串，矛盾