先给出公式 ans = n - LPS[n-1]
其中ans为最小周期,n为给出的由假设的周期字符串中提取出的子串长度,LPS为前缀函数,n-1为字符串最后的位置下标
证明如下
证明ans = n - LPS[n-1],思路:
(1) 证明特殊情况,即先对完整周期字符串进行证明,这时候的字符串组成是 [1][2][3][4] ,即4个周期拼接,所以由前缀函数的定义,有
[1][2][3] = [2][3][4],所以LPS[n-1] = 3*T,即三个周期,则ans = n(即4*T) - LPS[n-1] = 4*T - 3*T = T; 对于完整周期子串显然成立.
(2) 证明一般情况,即证明非完整周期字符串,假设给出的字符串是 [末部分][1][2][3][前部分] ,即中间有完整的周期,两边是不确定长度的,可能为0.
(为了方便,此处取[末部分] = [e],[前部分] = [b])
1,当len([e]) = len([b]) = 0时,即(1)的情况,显然成立. 2,当len([e]) = 0,len([b]) != 0时此时字符串为 [1][2][3][b],由于[b]是周期的一部分,则[3]中包含[b],有 [1][2][b] = [2][3][b],此时 LPS[n-1] = 2*T + len([b]), n = 3*T + len([b]),显然有 ans = n - LPS[n-1] == 3*T + len([b]) - 2*T - len([b]) = T,成立. 3,当len([b]) = 0,len([e]) != 0时同理. 4,当len([e]) != 0,且len([b]) != 0时,此时字符串为 [e][1][2][3][b],根据2,3,有 [e][1][2][b] = [e][2][3][b],符合前缀函数定义,此时LPS[n-1] = 2*T + len([b+e]),n = 3*T + len([b+e]) 显然有ans = n - LPS[n-1] = T,得证 5,当[e][b]内部没有完整的周期时,显然[e][b]可以自己组成最小周期,此时的LPS[n-1] = 0,ans = len([e+b]),为自己,得证
