【题目来源】
https://oj.czos.cn/p/2362

【题目描述】
给定若干由小写字母组成的字符串（这些字符串总长≤4×10^5），在每个字符串中求出所有既是前缀又是后缀的子串长度。例如：ababcababababcabab，既是前缀又是后缀的：ab，abab，ababcabab，ababcababababcabab。

【输入格式】
输入若干行，每行一个字符串。

【输出格式】
对于每个字符串，输出一行，包含若干个递增的整数，表示所有既是前缀又是后缀的子串长度。

【输入样例】
ababcababababcabab
aaaaa

【输出样例】
2 4 9 18
1 2 3 4 5

【数据范围】
字符串总长≤4×10^5。

【算法分析】
（一）运行超时及内存超限代码
substr(0,i)：截取下标 0 开始 i 个字符，不是截到下标 i。

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    while(cin>>s) {
        for(int i=1; i<=s.size(); i++) {
            string x=s.substr(0,i);
            string y=s.substr(s.size()-i);
            if(x==y) cout<<i<<" ";
        }
        cout<<endl;
    }

    return 0;
}

/*
in:
ababcababababcabab
aaaaa

out:
2 4 9 18
1 2 3 4 5
*/

（二）KMP解法
● 基于字符串下标从 1 计算这个前提，next[] 数组的涵义为：next[i] 表示字符串前 i 个字符的最长公共前后缀长度。

● 为什么递归 ne[] 数组就能找到所有答案？
答：字符串 ababcababababcabab 的 next数组值为：0 1 1 2 3 1 2 3 4 5 4 5 4 5 6 7 8 9。

ne[18] = 9 → 前 18 个字符的最长相等前后缀长度 = 9
ne[9] = 4 → 前 9 个字符的最长相等前后缀长度 = 4
ne[4] = 2 → 前 4 个字符的最长相等前后缀长度 = 2
ne[2] = 0 → 停止
所以所有答案：2 → 4 → 9 → 18

● KMP算法的next数组与前缀表的关系

【算法代码一】

#include <bits/stdc++.h>
using namespace std;

const int N=4e5+5;
int ne[N];

void getNext(string t) {
    int len=t.length();
    int i=0,j=-1;
    ne[0]=-1;
    while(i<len) {
        if(j==-1 || t[i]==t[j]) {
            i++,j++;
            ne[i]=j;
        } else j=ne[j];
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    string t;
    while(cin>>t) {
        int len=t.size();
        getNext(t);
        stack<int> st;
        int p=ne[len];
        while(p>0) {
            st.push(p);
            p=ne[p];
        }
        while(!st.empty()) {
            cout<<st.top()<<" ";
            st.pop();
        }
        cout<<len<<"\n";
    }

    return 0;
}

/*
in:
ababcababababcabab
aaaaa

out:
2 4 9 18
1 2 3 4 5
*/

【算法代码二】

#include <bits/stdc++.h>
using namespace std;

const int N=4e5+5;
int ne[N];

void getNext(string t) {
    int len=t.length();
    int i=0,j=-1;
    ne[0]=-1;
    while(i<len) {
        if(j==-1 || t[i]==t[j]) {
            i++,j++;
            ne[i]=j;
        } else j=ne[j];
    }
}

void print(int x) {
    if(x==0) return;
    print(ne[x]);
    cout<<x<<" ";
}

int main() {
    string t;
    while(cin>>t) {
        int len=t.size();
        getNext(t);
        print(ne[len]);
        cout<<len<<endl;
    }
    return 0;
}

/*
in:
ababcababababcabab
aaaaa

out:
2 4 9 18
1 2 3 4 5
*/

【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/160215718
https://blog.csdn.net/hnjzsyjyj/article/details/127140892
https://blog.csdn.net/hnjzsyjyj/article/details/146059543