kmp next数组

这题莽一看似乎是用扩展kmp做的。
事实上确实，我们可以利用扩展kmp完成
但是其实我们利用kmp就可以做出来了

我们已经知道了kmp中的next数组的意义
next[n]意义为最长的公共前缀和后缀
然后我们想知道下一个公共前缀和后缀了
一点就透答案是next[next[n]]循环就好了，直到为0

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int max_n = 4e5+100;
int n;
char p[max_n];
int net[max_n];
void getnext(){
    net[0]=-1;n=strlen(p);p[n]=500;
    for (int i=0,j=-1;i<n;){
        if (j==-1||p[i]==p[j])net[++i]=++j;
        else j=net[j];
    }
}

int main(){
    while (~scanf("%s",p)){
        vector<int> res;
        getnext();int cur = n;
        do{
            res.push_back(cur);
        }while (cur = net[cur]);
        while (!res.empty()){
            printf("%d ",res.back());
            res.pop_back();
        }puts("");
    }
}