很久之前我一直看不懂KMP算法，看了一个视频里dalao的讲解，我还是没看懂。。。。。。
然后在暑假的某一天，睡觉的时候突然明白了一点点我以前不会的KMP算法，于是赶紧记下来。
如果我希望得知某一个字符串 p 在某一个字符串 s 中是否出现过，或者出现过几次，或者在哪里出现过，那么应该怎么办呢？
BF算法
我上来一拍脑门就能想到一种暴力算法，也就是BF算法（Brute Force，也就是暴力算法），思路很简单，就是先把p和s左对齐比一比，不行就把p往后错一位比一比，以此类推，就像这样：
在上面的例子中，我们想在s串abcabcabdabba中找p串abcabd，方法就是先左对齐，慢慢把p往右挪一个个比，发现p在s中出现了一次。
分析它的时间复杂度，很明显，往右挪的次数大致是跟n成正比的，时间复杂度就是O(n)了。
那有没有更好的算法呢？
寻求改进：也许我不需要让P一步步挪
注：这里我的习惯是：认为字符串第一个字符的位置是1，而不是0。这意味着下文会认为字符串从1开始，而不是0。
基于刚才BF算法的暴力做法，我们可以考虑，如果希望它更快，那么我们应该直接考虑到的就应该是，如何减少它的步骤。
有三个科学家（D.E.Knuth，J.H.Morris和V.R.Pratt）对这种BF算法提出了自己的观点，因为他们觉得这样一点点挪太费劲，其实我没必要一点点挪，我一次挪动也许可以挪很多。就跟爬楼梯似的，想上快点那就一步跨好几个楼梯不就行了？
诶？这怎么讲呢？你怎么实现一次挪很多？
看下面这张图：
首先我们还是把p和s左对齐怼一怼，OK，在第6个位置那里一个是c，一个是d，这怼不上了。
要是我用BF算法去想，我还得往右挪一下。
但你想想这有必要嘛？
先简单的想一个这样的问题：p字符串开头是ab，而s字符串从2号位开始是bc，3号位开始是ca，到4号位开始才是ab，那我为啥不直接把p的1号位直接跟s的4号位对齐呢？
在上面的例子中，黄框的步骤根本没必要，我这样直接第一步就蹦到第四步了。
由此我们发现了一种让步骤变少的算法：观察我的字符串P，设匹配失败的位置是j，那么字符串P的字串 [1,j) 这段的开头和结尾，如果有一个公共字串，我就可以考虑来一个“大跳”，把P直接挪到这个公共字串上。这样中间可以省略掉很多步骤。
进一步考虑：这样具体怎样操作呢
我们给P串起个名字，叫模式串，现在我们有了这样的改进的解决问题初步想法：
- 先把P和S左对齐，从左开始比对一下，记录不匹配的位置j；
- 分析P串[1,j)这一段，找一个子串，使得[1,j)的前缀也是它，后缀也是它；
- 直接让P串前缀的位置卡到这个后缀的位置上，再次开始比对，循环下去。
OK，这样听起来很不错，我们的P再也不是一步步搓着走了，而能在可以的时候学会蹦好几步了。
我们为了方便起见，把第二步找的那个前缀和后缀都是它的子串起个名，叫[i,j)段的公共前后缀，简称公共串(这是本文为了称呼方便起的外号，不是正式名称)。
那么实施起来有这么几个问题：
选公共串有什么条件是什么？
刚才我们分析的过程找了ab这样一个公共串，这是怎么找出来的，我怎么不选别的，这有没有什么规则？
首先要明确的是，公共串与S串没有关系，只跟模式串P有关系。
然后呢，还有下面这三个注意点：
注意点1：前后缀允许有重叠部分
看下面这个例子：
模式串P为
xabxabxcdcdcdcdcd，P的第8个字符与S对应位置不匹配
在这个例子中，显然，我们要找的是P串[1,8)这一段上的公共前后缀：
经过我们的观察可以发现，满足这样的公共串是xabx，诶？前后缀重叠了？？？没事，前后缀重叠了也不影响我们往前挪P串啊，前后缀是可以有重叠部分的。
注意点2：优先最长的公共串，且其长度小于段长
这很好理解，我们应该让P在能挪动的范围内，往后挪的少一点，要不然往右挪的太多了，中间漏掉情况了咋办？
那怎么才能让P在能挪动的范围内往后挪的少呢？
如果[1,j)段上公共前后缀有多重可能性，我们应该选择那个公共前后缀最长，且长度小于段长的那个才可以，举个例子：
模式串P为
aaaaaaaabcdefg，P的第9个字符与S对应位置不匹配
在这个例子中我们要找[1,9)这一段上的公共前后缀。
那这可能性就多了去了，你可以认为公共前后缀是a，也可以认为是aa，也可以认为是aaa，也可以是aaaa，可以是aaaaa，或者aaaaaa，也能是aaaaaaa，也能说是aaaaaaaa，哪个好？
我们的规则：选最长的那个，并且长度小于[1,9)的段长，也就是小于8。
先说等于8的情况，这太简单了，要是等于段长的话不就相当于没挪？那你挪了个寂寞。
再说说上面其他七种情况，我们举前三个例子。
可以发现，选的公共串越长，P往后挪的越少。假如S是haaaaaaaabcdefg，实际上只需要P往后挪1位就够了，那你品一品，想匹配成功，公共串是不是得选较长的aaaaaaa(长度为7)？
怎么基于BF算法进行改进？
我们当前的思路就是，在BF算法的基础上加一个机制：如果匹配失败，卡的位置是j，找[1,j)公共前后缀，让P往右挪多一点，而不只是一个一个挪。
先把刚才的BF算法写出来：
public static boolean isContains(char[] s, char[] p, int n, int m) {
//i代表p的第1个字符与s的第几个字符相对
//j代表当前遍历到第几个字符了
int i = 1, j = 1;
while (i <= n && i + m - 1 <= n) { //头尾都没超过s的范围
boolean isSuccess = true; //标记当前匹配成功了没有
//这个while是匹配操作，每个都比一比
while (j <= m) {
if (s[i + j - 1] != p[j]) {
isSuccess = false;
break; //发现有一个字符不对应就改isSuccess
}
j += 1;
}
if (isSuccess) {
return true;//匹配成了
} else {
//没匹配成
i += 1;//右挪一个
j = 1; //j复原，下个位置从P的第一个位置继续看
}
}
//到头了啥也没匹配上就没有
return false;
}把没匹配成的位置改成上述思路，实现起来也比较简单：
public static boolean isContains(char[] s, char[] p, int n, int m) {
int i = 1, j = 1;
while (i <= n && i + m - 1 <= n) {
boolean isSuccess = true;
while (j <= m) {
if (s[i + j - 1] != p[j]) {
isSuccess = false;
break;
}
j += 1;
}
if (isSuccess) {
return true;
} else {
//没有匹配成功
int q = 0; //公共前后缀长度
//求最长公共前后缀长度
for (int k = 1; k < j - 1; k++) {
if (p[k] != p[j - k]) {
q = k - 1;
break;
}
}
int r = 1; //往后挪多少
if (q > 0) r = j - 1 - q;
i += r;
j = 1;
}
}
return false;
}这种查找子串的需求有很多种，上面举例说明了“判断子串是否存在”的例子，也可以改造成“判断子串出现了多少次”
public static int kmp(char[] s, char[] p, int n, int m) {
int i = 1, j = 1, t = 0;
while (i <= n && i + m - 1 <= n) {
boolean isSuccess = true;
while (j <= m) {
if (s[i + j - 1] != p[j]) {
isSuccess = false;
break;
}
j += 1;
}
if (isSuccess) {
t += 1;
i += 1;
} else {
int q = 0;
for (int k = 1; k < j - 1; k++) {
if (p[k] != p[j - k]) {
q = k - 1;
break;
}
}
int r = 1;
if (q > 0) r = j - 1 - q;
i += r;
}
j = 1;
}
return t;
}还可以改造成判断子串每次出现的位置，因为isSuccess判定为true的位置处i的值，就是当前P串最左侧与S串第i个字符相对的意思，所以位置判定是可以轻松实现的。
多次查找公共串长如何优化？
对于同一个[1,j)段而言，我们后面可能会求很多遍，这也会提高我们的时间复杂度。
那我们可以采用空间换时间的思路，我们在拿到P串的时候先构造一个数组，这个数组arr[j]告诉我们P串[1,j)段的公共串最长长度是多少，那么我们在实际运算的时候时间复杂度会降低很多。
现在，我们的思路越来越接近KMP算法的思想了。
但是还远远不够。
KMP算法
KMP算法提出P串叫做模式串，思想与上面是大同小异的，用到了空间换时间的思想。
这种方法一上来先用P串构建了其next数组。
什么是next数组？next数组就是我们刚才提到的[i,j)段最长公共串长度，
也就是如有next[j] = k，则有[1,j)段公共前后缀长度最大值为k。
由于for循环的写法更加简洁，实际应用KMP时，我还是比较喜欢for循环写法。
我还是以字符串第一个字符下标是1的思路来写一写。
第一步：实现KMP匹配过程
我们假设next数组已经做好了，设i是当前正在观察的S串位置，j是当前正在观察的P串位置的前一个位置，KMP的匹配过程应当可以这样实现：
for (int i = 1, j = 0; i <= n; i++) {
//j的减小意味着P串往右挪，这个while循环可以理解成一点点往右挪去尝试
while (j > 0 && s[i] != p[j + 1]) j = next[j];
//当前能匹配上，往右挪一个
if (s[i] == p[j + 1]) j++;
if (j == m) {
//todo 匹配成功了
j = next[j]; //匹配成功了再往右挪一下，继续查找
}
}其实这一实现就是对刚才的代码一系列的优化的结果（~同时也是我看网课抄的结果~）。
上面代码中我们的参照对象变化了，我们改成了移动j来控制P往右挪动，j的减小意味着P串往右挪动。
对j的操作有两种：
j = next[j]其实就是我们现在一直在讨论的大跳；j++其实就是右挪1位。
第二步：next数组的构建
先不做解释，看下面的next数组构建代码：
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && p[i] != p[j + 1]) j = next[j];
if (p[i] == p[j + 1]) j++;
next[i] = j;
}你会发现，诶？这不就跟上面的代码很相似吗？
这就是这种写法的精妙之处，其实next数组的求取本质上跟上面是一模一样的，只不过上面的操作是S串里找P串，现在换成了全部都在P串里。
不信？举个例子，比如，怎么能把某一段内的公共前后缀找出来？
方法就是把这两段上下摞起来，下面的一点点往右挪。假如abababab是从某个P串里抠出来的[1,9)段，动画展示一下效果就是这样怼的：
所以求next数组的本质就是一个匹配过程嘛！！！
完成！好耶！
由此终于完成了KMP算法的全部内容。
来做个题，这个就是AcWing上卡住我的那道题：
给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。输入格式
第一行输入整数N，表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M，表示字符串S的长度。
第四行输入字符串S。输出格式
共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。样例输入
3 aba 5 ababa样例输出
0 2
现在做起来so easy！
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
String p = scanner.next();
int n = scanner.nextInt();
String s = scanner.next();
kmp(
(" " + s).toCharArray(),
(" " + p).toCharArray(),
n,
m
);
}
public static void kmp(char[] s, char[] p, int n, int m) {
int[] next = new int[1008611];
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && p[i] != p[j + 1]) j = next[j];
if (i <= m && j <= m && p[i] == p[j + 1]) j++;
next[i] = j;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && s[i] != p[j + 1]) j = next[j];
if (i <= n && j <= m && s[i] == p[j + 1]) j++;
if (j == m) {
System.out.printf("%d ", i - m);
j = next[j];
}
}
}
}
OK，我点击提交代码！！！
TLE！！
哭了，为什么我费了这么多劲，怎么还是TLE！！！
原来是语言问题。
Java的Scanner比较慢，换成BufferReader和BufferWriter就好了。
import java.io.*;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
int m = Integer.parseInt(reader.readLine());
String p = reader.readLine();
int n = Integer.parseInt(reader.readLine());
String s = reader.readLine();
kmp(
(" " + s).toCharArray(),
(" " + p).toCharArray(),
n,
m
);
writer.flush();
writer.close();
reader.close();
}
public static void kmp(char[] s, char[] p, int n, int m) throws IOException {
int[] next = new int[1008611];
for (int i = 2, j = 0; i <= m; i++) {
while (j > 0 && p[i] != p[j + 1]) j = next[j];
if (i <= m && j <= m && p[i] == p[j + 1]) j++;
next[i] = j;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j > 0 && s[i] != p[j + 1]) j = next[j];
if (i <= n && j <= m && s[i] == p[j + 1]) j++;
if (j == m) {
writer.write(i - m + " ");
j = next[j];
}
}
}
}
大功告成！