return 0;
}
2.
<img src="https://raw.githubusercontent.com/XuandYu000/picture/main/20230826104627.png"/>
分析：答案为$n-next[n]$,一个字符串有着相同的前缀和后缀,此时将字符串长度减去最长公共前后缀长度所得到的就是一个循环覆盖，循环覆盖最小那么减去的最长公共前后缀最大。
```cpp
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e5+10;
char s[N];
int nxt[N];
void pre_kmp(char x[],int m)
{
int i,j;
j=nxt[0]=-1;
i=0;
while(i<m)
{
while(-1!=j&&x[i]!=x[j]) j=nxt[j];
nxt[++i]=++j;
}
}
void output(int a[],int m)
{
for(int i=0;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
scanf("%s",s);
pre_kmp(s,strlen(s));
// output(nxt,strlen(s));
printf("%d",strlen(s)-nxt[strlen(s)]);
return 0;
}
分析：将字符串加上#然后把原字符串翻转接入，求#之后最大的nxt[i]即为所求字符串的长度len，最后倒着输出前len个字符串即可
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <array>
using namespace std;
#define x first
#define y second
typedef pair<int, int> PII;
typedef long long LL;
const int N=1e5+10;
char s[N];
int nxt[N];
void pre_kmp(char x[],int m)
{
int i,j;
j=nxt[0]=-1;
i=0;
while(i<m)
{
while(-1!=j&&x[i]!=x[j]) j=nxt[j];
nxt[++i]=++j;
}
}
void output(int a[],int m)
{
for(int i=0;i<=m;i++) cout<<a[i]<<" ";
cout<<endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
scanf("%s",s);
int len=strlen(s);
s[len]='#';
for(int i=len+1,j=len-1;j>=0;j--,i++) s[i]=s[j];
// printf("%s",s);
pre_kmp(s,strlen(s));
// output(nxt,strlen(s));
int res=0;
for(int i=len+1;i<strlen(s);i++) res=max(res,nxt[i]);
for(int i=res-1;i>=0;i--) cout<<s[i];
cout<<endl;
return 0;
}
扩展kmp
解决问题：从字符串s第i位出发，可以最多匹配多少位p中的字符
朴素 \(O(nm)\)
直接从s的i位开始，p的0位按位找
扩展kmp(Z algorithm) \(O(n)\)
以线性时间复杂度求出一个字符串s和它的任意后缀\(s[i]\dots s[n]\)的最长公共前缀的长度
- 注意扩展kmp与kmp求出next数组的区别，前者是从字符s[i]开始,后者是从字符s[i]结束
算法流程：
计算完前i-1个z函数，维护盒子[l,r],s[l,r]=s[1,r-l+1]
- 如果\(i<=r\)(在盒内),则有s[i,r]=s[i-l+1,r-l+1]
- 若z[i-l+1]<r-i+1,则z[i]=z[i-l+1]
- z[i-l+1]>=r-i+1,则z[i]=r-i+1,从r+1后暴力枚举
- 如果\(i>r\)(在盒外),则从i开始暴力枚举
- 求出z[i]后，若i+z[i]-1>r，则更新l=i,r=i+z[i]-1
模板：
// nxt[i]:x[i……m-1]与x[0……m-1]的最长公共前缀
//extend[i]:y[i……n-1]与x[0……m-1]的最长公共前缀
void pre_KMP(char x[],int m,int nxt[])
{
nxt[0]=m;
int j=0;
while(j+1<m&&x[j]==x[j+1]) j++; //找x[1]与x[0……m-1]的最长公共前缀
nxt[1]=j;
int k=1;
for(int i=2;i<m;i++)
{
int p=nxt[k]+k-1; //盒子右边界
int L=nxt[i-k]; //盒子最左侧的的最长公共前缀
if(i+L<p+1) nxt[i]=L; // 在盒内且该点开始nxt最右侧位置并没有超过盒子最右侧
else //在盒外或者该点nxt的范围已经超过盒子的右侧
{
j=max(0,p-i+1);
while(i+j<m&&x[i+j]==x[j]) j++;
nxt[i]=j;
k=i;
}
}
}
void EKMP(char x[],int m,char y[],int n,int nxt[],int extend[])
{
pre_KMP(x,m,nxt);
int j=0;
while(j<n&&j<m&&x[j]==y[j]) j++;
extend[0]=j;
int k=0;
for(int i=1;i<n;i++)
{
int p=extend[k]+k-1;
int L=nxt[i-k];
if(i+L<p+1) extend[i]=L;
else
{
j=max(0,p-i+1);
while(i+j<n&&j<m&&y[i+j]==x[j]) j++;
extend[i]=j;
k=j;
}
}
}
例题
分析：利用z函数的性质找到extend[i]等于模式串长度的位置即可
```cpp
#include
#include
#include
#include
#include
#include
#include
#include 
现在把i向右移动一位会怎样？
- j不等于m且s[i+1]和p[j+1]一样，j也向右移动一位
- 否则j向前回到满足串s[i-k+1]$\dots$s[i]和p[1]$\dots$p[k]完全相等，且k的值最大的位置，然后继续判断
- 如果s[i+1]和p[j+1]仍不相同，则不停前退直至s[i+1]和p[j+1]相同或者j等于0为止