最长公共前后缀
字符串的前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。例如对于字符串 abacaba，其前缀有 a, ab, aba, abac, abacab，后缀有bacaba, acaba, caba, aba, ba, a。最长公共前后缀就是 aba。现给出一个长度为 N 的字符串 S，对于每个 M (0<=M<N)，求出连续子串 S[0…M] 的最长公共前后缀。
输入格式:
输入数据仅有一行，包含一个长度不超过 100,000 的仅由字母 a-z 构成的字符串。
输出格式:
对于每个 M (0,1,2,…,N−1)，输出对应的最长公共前后缀长度，以空格分隔，且行尾不得有多余空格。
输入样例:
abcdabcdabce
输出样例:
0 0 0 0 1 2 3 4 5 6 7 0
学过kmp算法的人都知道,最长公共前后缀数组求解出来后整体右移以为,最左面改为-1就是next数组,所以,这道题的实质就是求解next数组,然后不要从0下标输出,因为直接从一下标输出即可.因为原来next数组的求解中是不涉及最后一个下标的,所以next数组的循环条件需要比之前多1.这里可能大家不明白,不过没关系,好在我发现了一片写的特别好的博客,讲的清清楚楚,明明白白,我把链接发在这里,大家可以去看看.
july的kmp算法的博客,点击前往
代码如下:
#include<iostream>
#include<cstring>
using namespace std;
void GetNext(char *p,int *next){
int pLen=strlen(p);
next[0]=-1;
int k=-1;
int j=0;
while(j<pLen){
if(k==-1||p[k]==p[j]){
k++;
j++;
next[j]=k;
}else{
k=next[k];
}
}
}
int main(){
char str[100000];
cin>>str;
int next[100005];
GetNext(str,next);
int len=strlen(str);
for(int i=1;i<=len;i++){
if(i!=1)cout<<' ';
cout<<next[i];
}
}
