一、问题
给出两个字符串 \(s_1\) 和 \(s_2\)，若 \(s_1\) 的区间 \([l, r]\) 子串与 \(s_2\) 完全相同，则称 \(s_2\) 在 \(s_1\) 中出现了，其出现位置为 \(l\)。
现在请你求出 \(s_2\) 在 \(s_1\) 中所有出现的位置。
二、常规方法
对于平常的字符串匹配，我们一般会这样：
-
如果\(s1[i] = s2[j]\rightarrow i = i + 1,j = j + 1\)
-
否则\(i = i - j + 2, j = 1\)
即最平常的暴力算法
然而这种算法最坏是\(O(n\times m)\)的，无法接受
三、优化（即KMP)
我们可以先举个对上面方法非常不友好的栗子：
\(s_1 = {AAAAAAB}\)
\(s_2 = AAAB\)
每次\(s_2\)都要遍历到\(B\)才能发现不能匹配，显然很耗时间
从上面我们可以看出，因为\(B\)和\(A\)仅仅这一个不能匹配，便浪费了前面的\(3\)次匹配
那如何把前面的\(3\)次匹配利用起来呢？
我们可以发现，前面的\(AAA\)是匹配好的，为以示区分，记为\(A_1A_2A_3\)
\[A_1A_2A_3\ ?\\\Downarrow\\ \ \ \ \ \ \ \ \ \ \ A_1A_2A_3 \]如果能够只用判断没有判断过的 \(?\) 是否为\(A\)，那就会让复杂度减小很多
即我们在匹配失败(后记为失配)后如何移动下面的字符串的指针，这尤为重要
假使我们知道了这些数值，我们便可以在每一次失配的时候将指针向前跳。
那我们如何求这个指针跳跃的数组\(jump\)呢（简称失配数组）
其实\(jump_i\)就是去求在\(~1\to i~\)中最长的前缀等于后缀的长度
下面给一组例子：
| 下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 模式串 | A | B | A | B | A | B | C |
| 失配数组 | 0 | 0 | 1 | 2 | 3 | 4 | 0 |
| 前后缀 | 无 | 无 | A | AB | ABA | ABAB | 无 |
至于求法不太说得清楚，可以看一下下面的代码（抱歉）
#include<iostream>
#include<string>
using namespace std;
const int NN = 1e6 + 8;
string s1,s2;
int jump[NN];
int main(){
cin>>s1>>s2;
s1 = ' ' + s1;s2 = ' ' + s2;
if(s1.size() < s2.size())swap(s1,s2);
for(int i = 2, j = 0; i < s2.size(); ++i){
while(j > 0 && s2[i] != s2[j+1]) j = jump[j];//如果说不能匹配就跳回之前能匹配的位置
if(s2[i] == s2[j+1]) ++j;//否则j指针随i指针的右移而右移
jump[i] = j;
}//求失配数组
for(int i = 1,j = 0; i < s1.size(); ++i){
while(j > 0 && (j == s2.size() || s1[i] != s2[j+1])) j = jump[j];//失配就调回该进行匹配的地方
if(s1[i] == s2[j+1]) ++j;
if(j == s2.size()-1) printf("%d\n",i-s2.size()+2);
}//
for(int i = 1; i < s2.size(); ++i){
printf("%d ",jump[i]);
}
}