命题P：i %(i-next[i])==0 && next[i]!=0 
命题Q：S[i]是循环节字符串。
P是Q的充要条件。

一、必要性证明
我们先发现由循环节构成的字符串的性质：
假设前缀S[i]（S的长度为i的前缀）可以写成K（K>1）个循环节叠加（我们称这样的字符串叫做循环节字符串），并且这K个循环节在S中从左到右依次叫做S1,S2…,SK。那么：
M式：next[i]!=0成立，因为：
S1、SK可以做为next[i]的一个长度，所以next[i]!=0
N式：I %(i-next[i])==0成立，因为：
根据next的定义（以i结尾非前缀字串与S[i]前缀中，拥有最长的相同部分的两个），这个“最长的前缀”与“最长的后缀”可以是S1~Sk-1和S2~Sk,那么，应当有：i – next[i] = len(S1)，由于i=K*len(S1)，所以i % len(S1) = i % (i-next[i]) = 0。
Q -> P 得证

二、充分性证明
现在要证明P->Q，这样就可以通过命题P，O(1)判断是否Q成立。
证明：
 运用反证法，假设S[i]不是循环节字符串。
由于next[i]!=0的条件，那么S 必定存在最长的相同前、后缀，并且它们的长度不为0.
下面分类讨论：

i. next[i] < i / 2 （最长长度小于总长度一半）
那么， i – next[i] > i / 2 ，所以 i / (i – next[i]) 严格小于2，且显然大于1（next[i]!=0），所以M式不成立，矛盾；

ii. next[i] = i / 2 那么显然是由两个循环节构成的，矛盾。

iii. next[i] > i / 2 那么必定有重叠部分（重叠部分相等），记作S’。

那么S’的长度一定可以被(i-next[i])整除，计商为M，M>0。
所以，我们可以把S’分成M份，记作S’1,S’2,…S’M;另外，S可以背分做M+2段（重叠部分加首位两个），叫做S1，S2,…SM+2; 1~i-next[i]这部分字符串叫做A，也就是S1。

（概述一下证明思路：S1=A，由于next定义可知，S’1=A，又由重叠，S2=S’1=A；再有Next定义,S’2=S2=A…由此循环往复，即可知道S必定是由循环节构成的，循环结为A，与条件矛盾。）

下面用数学归纳法，证明Sj=A：

条件1：S’i= Si(Next定义)
条件2：S’i=Si+1（重叠部分相同）

基线条件：
S1 = A
S2 = S'1=S1 = A

递推条件：
假设Sk=A(k>1)成立，要证明Sk+1=A 成立;
那么，Sk+1=S'k=Sk=A，成立。
综上Sj=A得证，故S至少由A这一循环节构成。
故，与“假设：S不由循环节构成”矛盾，原命题不成立。
故，P->Q。
所以，Q与P构成充要条件。

• Re:判断循环的条件的简单证明 (29) J_Wang 2022-07-21 22:17:40