题目描述
给出两个字符串 s1 和 s2，若 s1 的区间 [l,r] 子串与 s2 完全相同，则称 s2 在 s1 中出现了，其出现位置为 l。
现在请你求出 s2 在 s1 中所有出现的位置。
定义一个字符串 s 的 border 为 s 的一个非 s 本身的子串 t，满足 t 既是 s 的前缀，又是 s 的后缀。
对于 s2，你还需要求出对于其每个前缀 ′s′ 的最长 border ′t′ 的长度。
输入格式
第一行为一个字符串，即为 s1。
第二行为一个字符串，即为 s2。
输出格式
首先输出若干行，每行一个整数，按从小到大的顺序输出 s2 在 s1 中出现的位置。
最后一行输出 ∣s2∣ 个整数，第 i 个整数表示 s2 的长度为 i 的前缀的最长 border 长度。
输入输出样例
输入 #1
ABABABC ABA
输出 #1复制
1 3 0 0 1
说明/提示
样例 1 解释
。
对于 �2s2 长度为 33 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 11。
数据规模与约定
本题采用多测试点捆绑测试，共有 3 个子任务。
- Subtask 1（30 points）：∣s1∣≤15，∣s2∣≤5。
- Subtask 2（40 points）：∣s1∣≤104，∣s2∣≤102。
- Subtask 3（30 points）：无特殊约定。
对于全部的测试点，保证 1≤∣s1∣,∣s2∣≤106，s1,s2 中均只含大写英文字母。
很适合拿来对KMP进行深度化理解的模板
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M=4e4+10;
const int N=1e6+10;
int Next[N];
void getNext(string str)
{Next[0]=-1;Next[1]=0;int i=2;int cn=0;while(i<=str.size()){if(str[i-1]==str[cn])Next[i++]=++cn;else if(cn>0)cn=Next[cn];elseNext[i++]=0;}
}
void KMP(string str1,string str2)
{getNext(str2);int i1=0;int i2=0;while(i1<str1.size()){if(str1[i1]==str2[i2]){i1++;i2++;}else if(i2>0)i2=Next[i2];elsei1++;if(i2==str2.size()){cout<<i1-str2.size()+1<<endl;i2=Next[i2];}}
}
void solve()
{string s1,s2;cin>>s1>>s2;KMP(s1,s2);for(int i=1;i<=s2.size();i++)cout<<Next[i]<<" ";cout<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
// cin>>t;while(t--){ solve();}return 0;
}
