题目描述
给出两个字符串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 长度。
输入输出样例
输入
ABABABC
ABA
输出
1
3
0 0 1
题意分析就是让我们先找出第二的前后缀最长的公共子串，然后输出，最后利用这个找到第二个字符串在第一个字符串里面的位置，输出即可，kmp，这种思想要理解。具体思想看代码。
#include<bits/stdc++.h> const int MAXN=1e7+10; using namespace std; int kmp[MAXN]; int la,lb,j; char a[MAXN],b[MAXN]; int main() { cin>>a+1;//输入字符串s1 意思就是从下标1 cin>>b+1;//输入字符串s2 la=strlen(a+1);//长度相当于有几个字母注意 lb=strlen(b+1); for (int i=2;i<=lb;i++)//j控制kmp[j] 要小 { while(j&&b[j+1]!=b[i])//j不为0且如果不相邻就跳到前一个前缀里面把j j=kmp[j]; if(b[j+1]==b[i])//如果相等 j++; kmp[i]=j;//前缀数 } j=0; for(int i=1;i<=la;i++) { while(j>0&&b[j+1]!=a[i]) j=kmp[j]; if (b[j+1]==a[i]) j++; if (j==lb) { cout<<i-lb+1<<endl; j=kmp[j];//回溯把kmp的前缀拿出来 } } for (int i=1;i<=lb;i++) cout<<kmp[i]<<" ";//打印的是每个数的前缀 }
