东方博宜OJ 2391：子串位置 ← KMP算法

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

【题目描述】
给定一个父字符串 s 和子字符串 p，请按照从前向后的顺序，请求出 p 在 s 中所有出现的起始位置。
例如：S=ABADABCEABABA，P=ABA，则求解的结果是：1 9 11。

【输入格式】
第 1 行读入一个仅包含大写字母的字符串 s；
第 2 行读入一个仅包含大写字母的字符串 p；
s 和 p 均是长度不超过 10^6 的字符串。

【输出格式】
输出 1 行，按题意输出 p 在 s 中出现的位置，数字之间用空格隔开。

【输入样例】
ABADABCEABABA
ABA

【输出样例】
1 9 11

【数据范围】
s 和 p 均是长度不超过 10^6 的字符串。

【算法分析】
● KMP算法详见：https://blog.csdn.net/hnjzsyjyj/article/details/146059543

●​​​​​​​ 在本文 KMP 函数的定义中，只需在 if(j==lent) 时，修改 j 的值，便可实现不重叠（j=0）及重叠（j=ne[j]）计算模式串在主串中出现的次数。 
（1）题目“HDU 2087：剪花布条 → https://blog.csdn.net/hnjzsyjyj/article/details/127140892”，不重叠计算模式串在主串中出现的次数。（if(j==lent), j=0）
（2）题目“HDU 1686：Oulipo → https://blog.csdn.net/hnjzsyjyj/article/details/134238575”，重叠计算模式串在主串中出现的次数。（if(j==lent), j=ne[j]）

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int N=1e6+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 KMP(string s,string t) {int lens=s.length(),lent=t.length();int i=0,j=0;while(i<lens && j<lent) {if(j==-1 || s[i]==t[j]) {i++,j++;} else j=ne[j];if(j==lent) {cout<<i-j+1<<" ";j=ne[j];}}
}int main() {string s,t;getline(cin,s);getline(cin,t);getNext(t);KMP(s,t);return 0;
}/*
in:
ABADABCEABABA
ABAout:
1 9 11
*/

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