KMP算法——寻找子串位置
1、KMP算法简介：
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度时间复杂度)O(m+n)。
2、什么是字符串匹配：
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
在Java中就是String的indexOf()方法。
3、对比暴力法和KMP算法：
首先我们可以比对一下暴力法和KMP算法的差距：
（1）暴力法
挨个截取遍历字符串，然后对比
（2）KMP算法
若遇到不匹配的，则会跳转到最小公共子串以后的地方进行匹配，会跳过中间不匹配的步骤，从而简化了时间复杂度。但是也都是空间换时间
这块声明一下，暴力法中的每一个字符匹配（连接的黑色剪头）是挨个匹配的，我是写到了一起，其实是很多步的；而KMP是直接跳转到最后一步的，跳过了公共子串的判断，可能是案例比较经典，跳转过来之后，就可以直接排除当前情况了。
感受玩KMP算法的魅力，现在开始操作起来，接收这愉快的“解题”环节（更像是受虐）。
4、KMP算法实现：
KMP算法一般分为两步：
- 提取加速匹配的信息（构造next数组），也是本算法中最难的部分。
- 字符串的匹配
4.1、提取加速匹配的信息（构造next数组）
KMP之所以可以跳过很多公共子串的匹配，是因为它的next数组里面记录了从当前下标位置，往前判断，找到最长公共子串的最后一个位置。
用数学语言表述：本文中的最小公共子串的概念，不是官方的定义，就自己读起来顺畅。
对于每模式串 t 的每个元素 t j，都存在一个实数 k ，使得模式串 t0 开头的 k 个字符
依次与 t j 前面的 k
，这里第一个字符 t j-k 最多从 t 1 开始，所以 k < j）个字符相同。如果这样的 k 有多个，则取最大的一个。
图解：
对于元素t5，存在一个实数2，使得模式串t0开头的2个字符 t0 t1，依次与t3和t4相同。
如果在匹配过程中，到t5的时候，和目标串不匹配了，此时就可以模式串回调到t2的位置，接着判断匹配。
因为t0 t1 是最大重复子串，所以就可以跳过判断，直接判断t2和当前目标字符串的字符是否匹配。
图解：
首先，先需要了解一下next数组，存放的是什么东西？
next数组其实就是存放着一个回调的位置，意思就是如果我匹配模式串的时候，假如到 t[i] 位置的时候不匹配了，那么我应该跳转到那个位置，接着对比匹配，可以跳过重复子串的判断。
例如上述案例，next[5] = 2
注意：next数组只和模式串有关系，和目标串没有关系。就算没有目标串，模式串也有next数组。
如果看到这块，你能够理解next的功能，恭喜你，你已经完成成功路程的一半了。
下来我们来一起探索一下，next数组应该如何得到？
首先，先拿到我们的模式串：我们的next数组的大小就是模式串pat的长度。
分为如下三种情况，来计算next的值：
我们用j来遍历模式串pat，初始值为0，用k作为临时变量，初始值为-1，来计算next[j]的值。
我们可以根据上面的理解可以直接写出来，next数组，但是，要怎样设置算法让计算机计算呢？
（1）特殊情况：
当j为0的时候，，next[0] = -1，目的是方便我们后面的计算。
当j为1的时候，pat[0]就是他的最小子串，所以next[1] = 0;
（2）当 pat[j] == pat[k] 或者 k == -1 的情况:
说明目前遍历到字符串为首元素，或者就是遍历到的字符和k所指向的位置元素相同，每次都是从字符串串首开始的，所以k的含义，不仅是记录下标位置，还有最长公共子串的长度。
这块的最长公共子串，是自己的定义，意思是pat[0] pat[1]…… pat[k] 字符串和 pat[j-k] pat[j-k+1]…… pat[j] 相同。
遇到这种情况，就让j++，k++，next[j] = k
这块注意，为什么我们判断的是pat[j] == pat[k]，而要给next[j] = k++，因为我们next里面存放的是遇到不匹配的时候，要回调的位置，因为0到k的位置已经是匹配的了，所以我们直接跳转到k+1的位置，我们就给next[j] = k++。
（3）其他情况：也就是k的位置与j的位置不匹配
我们直到如果不匹配的话，就需要调用回调，让k的值回调。我们计算的next数组就是用来回调的。
让 k = next[k]
让k回调了之后，再次进入循环，若k的位置与j的位置还是不匹配，那么k就继续回调，直到k=-1，会满足第二种情况，即给next[j] = 0。
因为逻辑性很强，所以希望参考代码理解。
代码：
void Getnext(int next[],String pat)
{
if(pat.length()==0) {
next = new int[]{0};
return;
}
next = new int[pat.length()];
int j = 0, k = -1;
next[0] = -1;
while (j < pat.length() - 1) {
if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
j++;
k++;
next[j] = k;
} else
k = next[k]; //k回调
}
}
4.2 字符串的匹配
当我们拿到next数组的时候，后面使用的时候会十分简单！！！
我们用 i 和 j 分别遍历 目标字符串s和模式串pat
我们这次只需要一个单层循环，这也是和暴力法降低时间复杂度最根本的地方。
单层循环：while( i<s.length()&&j<pat.length() )
- 当
s[i] == pat[j]时，说明当前的字符匹配，i++;j++； - 当
s[i] != pat[j]时，说明当前的字符不匹配，让j进行回调，即j = next[j];
不满足条件退出循环
- 当
j>=pat.length()时，说明已经找到模式匹配的子串了，直接return 找到的位置，即return i-pat.length(); - 否则，说明没有找到模式匹配的子串，直接
return -1;
代码：
public int indexOf(String s)
{
if(pat.length()==0) {
return 0;
}
int i=0,j=0;
while(i<s.length()&&j<pat.length())
{
if(j==-1 || s.charAt(i) == pat.charAt(j))
{
i++;
j++;
}
else j=next[j]; //j回调
}
if(j>=pat.length())
return (i-pat.length()); //匹配成功，返回子串的位置
else
return (-1); //没找到
}
5、KMP完整代码：
void Getnext(int next[], String pat) {
next = new int[pat.length()];
int j = 0, k = -1;
next[0] = -1;
while (j < pat.length() - 1) {
if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
j++;
k++;
next[j] = k;
} else
k = next[k]; // k回调
}
}
int indexOf(String s) {
int i = 0, j = 0;
while (i < s.length() && j < pat.length()) {
if (j == -1 || s.charAt(i) == pat.charAt(j)) {
i++;
j++;
} else
j = next[j]; // j回调
}
if (j >= pat.length())
return (i - pat.length()); // 匹配成功，返回子串的位置
else
return (-1); // 没找到
}
6、利用面向对象封装
package com.company.project.arithmetic;
public class KMP {
private int[] next;
private String pat;
/**
* 在构造方法中计算next数组
* @param pat 模式串
*/
public KMP(String pat) {
this.pat = pat;
if(pat.length()==0) {
next = new int[]{0};
return;
}
next = new int[pat.length()];
int j = 0, k = -1;
next[0] = -1;
while (j < pat.length() - 1) {
if (k == -1 || pat.charAt(j) == pat.charAt(k)) {
j++;
k++;
next[j] = k;
} else
k = next[k];
}
}
/**
* 寻找子串位置
* @param s 目标串
* @return
*/
public int indexOf(String s) {
if(pat.length()==0) {
return 0;
}
int i = 0, j = 0;
while (i < s.length() && j < pat.length()) {
if (j == -1 || s.charAt(i) == pat.charAt(j)) {
i++;
j++;
} else
j = next[j]; // j回退。。。
}
if (j >= pat.length())
return (i - pat.length()); // 匹配成功，返回子串的位置
else
return (-1); // 没找到
}
public static void main(String[] args) {
KMP kmp = new KMP("");
for (int i = 0; i < kmp.next.length; i++) {
System.out.println(kmp.next[i]);
}
String s = "abababcabd";
System.out.println("result:" + kmp.indexOf(s));
}
}
