以下代码是求解 next 数组的大致过程
//j-->前缀末尾的位置,也代表着 i之前，包括 i的子串的最长相等前后缀的长度
//i-->后缀末尾的位置
//ne[i]-->字符串s[0,i] 中的最长相等前后缀长度
cin>>n>>s;
next[0]=0; int j=0;//初始化
for(int i=1;i<s.size();i++)// i = 1是因为字符串下标是从0开始的
{
while(j>0&&s[i]!=s[j])//前缀末尾和后缀末尾不匹配的时候,j要向前回退，也就是j看它前一位的next数组的值，所对应的值就是要回退到的下标
j=next[j-1];
if(s[i]==s[j])//前后缀相同情况
j++;
next[i]=j;//更新next数组
}
##########################
//字符串的下标是从1开始的代码
cin>>n;
cin>>s+1;
int j=0;
ne[1]=0;
for(int i=2;i<=n;i++)
{
while(j>0&&s[i]!=s[j+1]) j=ne[j];
if(s[i]==s[j+1]) j++;
ne[i]=j;
//cout<<ne[i]<<"\n";
}
@@@@@@@@@@@@@@@@@@
//最长相等前后缀数组整体向右移动一位，初始值为 -1 的代码
cin>>n>>s;
int j=0,k=-1;
ne[0]=-1;
while(j<n)
{
if(k==-1||s[j]==s[k])
{
k++;
j++;
ne[j]=k;
}
else
k=ne[k];
}
/*
步骤：
1.初始化
2.前后缀不同的情况
3.前后缀相同的情况
4.更新next数组