【题目来源】https://oj.czos.cn/p/2362【题目描述】给定若干由小写字母组成的字符串这些字符串总长≤4×10^5在每个字符串中求出所有既是前缀又是后缀的子串长度。例如ababcababababcabab既是前缀又是后缀的abababababcababababcababababcabab。【输入格式】输入若干行每行一个字符串。【输出格式】对于每个字符串输出一行包含若干个递增的整数表示所有既是前缀又是后缀的子串长度。【输入样例】ababcababababcababaaaaa【输出样例】2 4 9 181 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(cins) { for(int i1; is.size(); i) { string xs.substr(0,i); string ys.substr(s.size()-i); if(xy) couti ; } coutendl; } 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。idx123456789101112131415161718Tababcababababcababne[]011231234545456789ne[18] 9 → 前 18 个字符的最长相等前后缀长度 9ne[9] 4 →前 9 个字符的最长相等前后缀长度 4ne[4] 2 →前 4 个字符的最长相等前后缀长度 2ne[2] 0 → 停止所以所有答案2 → 4 → 9 → 18● KMP算法的next数组与前缀表的关系【算法代码一】#include bits/stdc.h using namespace std; const int N4e55; int ne[N]; void getNext(string t) { int lent.length(); int i0,j-1; ne[0]-1; while(ilen) { if(j-1 || t[i]t[j]) { i,j; ne[i]j; } else jne[j]; } } int main() { ios::sync_with_stdio(0); cin.tie(0); string t; while(cint) { int lent.size(); getNext(t); stackint st; int pne[len]; while(p0) { st.push(p); pne[p]; } while(!st.empty()) { coutst.top() ; st.pop(); } coutlen\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 N4e55; int ne[N]; void getNext(string t) { int lent.length(); int i0,j-1; ne[0]-1; while(ilen) { if(j-1 || t[i]t[j]) { i,j; ne[i]j; } else jne[j]; } } void print(int x) { if(x0) return; print(ne[x]); coutx ; } int main() { string t; while(cint) { int lent.size(); getNext(t); print(ne[len]); coutlenendl; } return 0; } /* in: ababcababababcabab aaaaa out: 2 4 9 18 1 2 3 4 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/160215718https://blog.csdn.net/hnjzsyjyj/article/details/127140892https://blog.csdn.net/hnjzsyjyj/article/details/146059543