先给出公式 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]),为自己,得证 附上例题加以理解:
1,KMP算法模板https://www.luogu.com.cn/problem/P3375
2,字符串周期模板题https://www.luogu.com.cn/problem/P4391
例题1代码解析:
点击查看代码
//背景:刚学LPS函数及其应用KMP,先来道模板题练习,结果发现细节多 //注意:以后我的所有关于KMP的算法的字符串下标均是从0开始(便于与OI-wiki统一,好记忆) //原理:KMP匹配字符串 //时间复杂度:o(n+m) #include <bits/stdc++.h> using namespace std; void Prefixion(int LPS[],string s)//求生成字符串的前缀函数 { LPS[0] = 0;//初始化前缀 for (int i = 1,big = s.size();i<big;i++)//遍历字符串 { int j = LPS[i-1];//获取上一个位置的LPS while(j>0&&s[j] != s[i]) j = LPS[j-1];//寻找第一个使得当前位置i的前缀性质仍满足的j if(s[j] == s[i]) j++;//如果是因为相等退出循环的,j是位置,那么长度为j+1 LPS[i] = j;//记录当前位置的LPS } } void KMP()//KMP算法 { string text,pattern; cin>>text>>pattern;//输入文本字符串及模板字符串(待查找的字符串) string cur = pattern + '#' + text;//生成新的字符串 int s1 = pattern.size();//计算模板字符串的长度 int s2 = text.size();//计算文本字符串的长度 int LPS[s2+s1+1];//注意这里LPS的数组大小,如果开小了退不出函数(我也不知道为什么) Prefixion(LPS,cur);//求生成字符串的前缀函数 vector<int> occurrence;//记录文本字符串匹配成功的起始位置 for (int i = s1+1;i<=s2+s1;i++)//从生成字符串的文本位置开始遍历 { if(LPS[i] == s1) occurrence.push_back(i-2*s1);//如果满足当前情况,即记录下成功匹配的位置(相对文本):当前位置 - 2*模板长度 } for (auto v:occurrence) cout<<v+1<<"n";//依次输出位置(相对文本的) for (int i = 0;i<s1;i++) cout<<LPS[i]<<" ";//输出每个前缀的函数值 cout<<"n"; } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; while(t--) { KMP(); } return 0; } 例题2代码解析:
点击查看代码
//背景:字符串的周期性问题,一开始不太理解,后来看了题解自己画图推导出来了 //本题题意:本题给出的是重复拼接字符串子串,求最小周期,也就是说假定了原字符串是周期函数,给分析证明提供了思路 //公式:ans = n - LPS[n-1] #include <bits/stdc++.h> using namespace std; void Prefixion(int LPS[],string s)//前缀函数 { LPS[0] = 0;//不要忘了初始化 for (int i = 1;s[i] != ' ';i++) { int j = LPS[i-1]; while(j > 0&&s[j] != s[i]) j = LPS[j-1]; if(s[j] == s[i]) j++; LPS[i] = j; } } void Solve() { int n; string s; cin>>n;//输入子串长度 cin>>s;//输入字符串 int LPS[n];//定义前缀函数 Prefixion(LPS,s);//求前缀函数 cout<<n - LPS[n-1]<<"n";//输出最小周期 } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t = 1; while(t--) { Solve(); } return 0; } /*证明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]),为自己,得证 码字不易,多多支持!
