企业官网建设流程全解析

【题目来源】
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