}

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]

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后暴力枚举
2. 如果\(i>r\)(在盒外),则从i开始暴力枚举
3. 求出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;
		}
	}
}

例题

2. 
<img src="https://raw.githubusercontent.com/XuandYu000/picture/main/20230826171515.png"/>
分析:找到p即是s前缀又是s后缀只需当前位置i加上nxt[i]为字符串长度即可，至于以非前后缀出现过则要求存在nxt[i]大于求得的最长位置即可
```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=1e6+10;
char s[N];
int len,nxt[N];
void pre_EKMP(char x[],int m,int nxt[])
{
	nxt[0]=m;
	int j=0;
	while(j+1<m&&x[j]==x[j+1]) j++;
	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;
		else
		{
			j=max(0,p-j+1);
			while(i+j<m&&x[i+j]==x[j]) j++;
			nxt[i]=j;
			k=i;
		}
	}
	int res=0,maxn=0;
	for(int i=0;i<m;i++)
	{
		if(i+nxt[i]==m)
			if(maxn>=nxt[i])
				res=max(res,nxt[i]);
		maxn=max(maxn,nxt[i]);
	}
	if(!res) printf("Just a legend\n");
	else
	{
		for(int i=0;i<=res;i++) printf("%c",s[i]);
		puts("");
	}
}
int main()
{
	scanf("%s",s);
	len=strlen(s);
	pre_EKMP(s,len,nxt);

	return 0;
}