先给出公式 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算法模板
2,字符串周期模板题
例题1代码解析:
//背景:刚学lps函数及其应用kmp,先来道模板题练习,结果发现细节多
//注意:以后我的所有关于kmp的算法的字符串下标均是从0开始(便于与oi-wiki统一,好记忆)
//原理:kmp匹配字符串
//时间复杂度:o(n m)
#include
using namespace std;
void prefixion(int lps[],string s)//求生成字符串的前缀函数
{
lps[0] = 0;//初始化前缀
for (int i = 1,big = s.size();i0&&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 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<ain()
{
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
using namespace std;
void prefixion(int lps[],string s)//前缀函数
{
lps[0] = 0;//不要忘了初始化
for (int i = 1;s[i] != '\0';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<
