KMP算法
1. 引入
KMP算法中最著名的应用便是 “求子串问题”。
标题：
现在有str1=”abcd1234efg” 和str2=”1234″，怎么判别str2是不是str1的子串？
留意，子串有必要是接连一段，比方 “1234f” 就不是 “abcd1234efg” 的子串，可是 “1234e” 是。
剖析：
本题假如运用暴力解法，则测验办法是从左往右测验str1中每一个字符是否能够配出str2。
暴力解法在一种极端的状况下，时刻复杂度会十分高。比方：str1=”1111111112″，str2=”11112″。假如要用暴力解法，则str1从榜首个字符1向后配了5次发现配不上，再从第二个字符1向后又配了5次发现配不上，以此类推，直到str1最终一段才配上。假如str1长为N，str2长为M，则时刻复杂度为O(NM)，相当于str1每走一步就需求遍历整个str2。
假如运用KMP算法处理该问题，则回来类型不是boolean，而是回来子串在str1中榜首个字符的下标，假如不包括回来-1。
KMP和暴力解法核心思维是相同的，都是从左往右测验str1中每一个字符是否能够配出str2，可是KMP有加快。
暴力解法：
public static boolean findSubStr(String str1, String str2) {
if (str1 == null || str2 == null || str1.length < str2.length) {
return false;
}
return process(str1.toCharArray(), str2.toCharArray());
}
public static boolean process(char[] c1, char[] c2) {
// 标记默以为false，这样假如str1和str2一个相交字符都没有也会回来false
boolean flag = false;
// 遍历整个str1
for (int i = 0; i < c1.length; i ++) {
// 测验str1中每一个字符和str2相匹配
if (c1[i] == c2[0]) {
// 只需有一个字符匹配上，咱们就期望这次匹配是成功的
flag = true;
// str1和str2挨个字符进行匹配
int k = i + 1;
for (int j = 1; j < c2.length; j ++, k ++) {
// 在匹配进程只需有一个字符不相同匹配就失利，直接停止匹配
if (c1[k] != c2[j]) {
flag = false;
break;
}
}
}
}
return flag;
}
2. 最大匹配长度
在将KMP算法处理 “求子串问题”，咱们首要要理解一个概念，便是最长前缀和后缀的匹配长度。
最长前缀和后缀的匹配长度是子串（str2）中每一个字符都需求带着的信息，该信息与对应的字符无关，可是与对应字符的前面所有字符有关。
比方说有一个字符串 “abbabbk”，咱们想要知道k字符的最长前缀后后缀的匹配长度。
首要咱们需求获取k字符前面的字符串 “abbabb”，然后求出 “abbabb” 字符串前缀和后缀的最大匹配长度为3，k字符带着的信息便是3。
前缀和后缀都不能取到字符串全体。
假如该字符前面没有字符串，则该字符带着的信息便是 -1。
人为规则字符串0方位的字符带着的是 -1，1方位的字符带着的是0。
3. 加快流程
运用KMP加快该问题的关键是：str2中每一个字符要带着前缀和后缀的最大匹配长度。
假定str1=”……oabbcefabbckbc……”，str2=”abbcefabbcg……”。str1中显示的首字符o是第 i – 1 位，假定当时str1从第 i 位开端开端匹配str2（前面匹配进程疏忽）。
运用经典办法：
str1的第 i 位之后的字符顺次和str2进行字符匹配，在str1匹配到第 i + 10 位时，发现和str2第 10 位的字符匹配不上，从第 i 位开端的匹配操作失利。因而，str1就会抛弃第 i 位能匹配子串成功的可能性，匹配指针会从str1的第 i + 10 位跳到第 i + 1位，第 i + 1之后的字符顺次再和str2第 0 位字符进行字符匹配（相当于str2向右滑动一位）。以此类推。
运用KMP算法加快：
计算str2中每个字符的前后缀最大匹配长度： [ -1，0，0，0，0，0，0，1，2，3，4 …… ]。
str1的第 i 位之后的字符顺次和str2进行字符匹配，在str1匹配到第 i + 10 位时，发现和str2第 10 位的字符匹配不上，从第 i 位开端的匹配操作失利。
依据计算的前后缀最大匹配长度可知，其间前 11 位中最大匹配长度为第 10 位字符对应的4，因而能够确定在str2第 10 位字符g之前最大前缀和最大后缀是 “abbc”。
str1的匹配指针不动，持续和str2的第 4 位（最大前缀的后一位）进行字符匹配。
4. 剖析
要想理解KMP的第二部操作究竟什么意思？经过查看两次的比较目标就能够得知。
和经典办法相同，在str1第 i 位开端的匹配操作失利之后，str1也不会再去测验第 i + 1 位能够匹配成功的可能性，可是str1不会去测验第 i + 2 位能够匹配成功的可能性，而是直接测验第 i + 6 位能够匹配成功的可能性（相当于str2向右滑动（最大后缀中榜首位的下标 – 最大前缀榜首位的下标）位），也便是说str1会直接从str1中的str2的最大后缀开端匹配。
可是str1第 i + 6 位和str2第 0 位开端往后4位在上一轮匹配中就确定是重合的了，都是最大前 / 后缀的内容为 “abbc”。为了加快效果更好（常数加快），在实践比较时能够直接越过重合部分进行开端比较。
因而str1并没有从第 i + 6开端测验匹配，而是直接从第 i + 11位开端匹配，由于str1的第 i + 6 位到第 i + 9 位和str2的第 0 位到第 3 位是重合的，只要到str1的第 i + 10 位之后才可能会呈现匹配失利的状况。
那么现在需求证明一点：为什么从str1的第 i + 1 位到第 i + 5 位开端匹配就必定会匹配失利？
5. 证明
为什么从str1的第 i + 1 位到第 i + 5 位开端匹配就必定会匹配失利？
仍是和str2计算的第 0 位到第 10 位字符每个字符的前后缀最大匹配长度这个数组 [ -1，0，0，0，0，0，0，1，2，3，4 …… ] 有关。
将上述证明问题抽象：证明str1的第 i 位到第 j 位 [ i+1，j-1 ] 中心任何一位 k 开端匹配都必定会失利。
该证明有一个前提条件：从str1的第 i 位到第 (X – 1) 位这一段和从str2的第 0 位到第 (Y – 1) 位这一段彻底持平。
运用反证法，假定str1的第 k 位开端匹配，结果匹配成功。
已知，str1无论是从哪一位开端匹配都是从str2的第 0 位开端匹配的，假如匹配成功，意味着从str1的第 k 位开端一向到第 X 位这一段必定和从str2第 0 位开端到第 (X – k) 位这一段彻底一致。
因而，从str1的第 k 位开端一向到第 (X -1) 位这一段必定和从str2的第 0 位开端到第 (X – k – 1) 位这一段彻底一致。
又由于上一轮顺位匹配时只要str1第 X 位和str2第 Y 位不同，因而从str1的第 k 位到第 (X -1)位这一段必定和从str2的第 (Y – X + K) 位到第 (Y – 1) 位这一段必定彻底一致。
由等价交换，从str2的第 0 位开端到第 (X – k – 1) 位这一段和从str2的第 (Y – X + K) 位到第 (Y – 1) 位这一段必定彻底一致。
由于str1的第 k 位小于第 j 位，因而从str1的第 k 位到第 X 位这一段必定比从第 j 位到第 X 位这一段要大。
因而对应的从str2的第 0 位开端到第 (X – k – 1) 位这一段必定比原第 Y 位的最长前缀要长。
由于从str2的第 0 位开端到第 (X – k – 1) 位这一段和从str2的第 (Y – X + K) 位到第 (Y – 1) 位这一段等长。
因而对应的从str2的第 (Y – X + K) 位到第 (Y – 1) 位这一段必定比原第 Y 位的最长后缀要长。
又由于从str2的第 0 位开端到第 (X – k – 1) 位这一段也相当所以第 Y 位的前缀，从str2的第 (Y – X + K) 位到第 (Y – 1) 位这一段也相当所以第 Y 位的后缀。
所以原str2的第 Y 位呈现了一个比最长前缀和后缀更长的前缀和后缀，由于现已给出了最长前缀和后缀，所以相互对立，假定不成立。
6. 完好流程
实践上KMP的整个流程便是str2一向右移的进程。
咱们抛开KMP常数优化的进程，仔细剖析一下KMP加快的本质流程。
KMP为什么很快？拿str1中a~e举比如，运用经典办法需求比较17次，而运用KMP只需求比较4次，假如加上KMP的常数加快，那么在4次比较中将会更快。
其间，①、②、③和④是4次匹配开端时str1和str2的比较方位，实践上代表了KMP对str1中a~e这一段完好的加快流程。
在匹配指针指向str1的①方位开端匹配时，直到发现 e 和 w 匹配不上，因而①方位匹配失利。
然后找出str2中 w 的最长前后缀为：abbsabb。匹配指针指向②方位开端匹配，直到发现 e 和 t 匹配不上，因而②方位匹配失利。
然后找出str2中 t 的最长前后缀为：abb。匹配指针指向③方位开端匹配，直到发现 e 和 s 匹配不上，因而③方位匹配失利。
然后找出str2中 s 的最长前后缀为：无。匹配指针指向④方位开端匹配，发现 e 和 a 匹配不上，因而④方位匹配失利。
str1中a~e现已悉数和str2匹配完，任何一个方位开端匹配都匹配不出str2，因而匹配指针指向 e 的后面一位⑤开端匹配，持续循环执行①方位的操作，周而复始，直到str1最终一位结束。
7. 实现
该实现进程包括了常数加快进程。
// 回来值是子串在str1中的起始下标
public static int findSubStr(String str1, String str2) {
if (str1 == null || str2 == null || str1.length() < str2.length()) {
return -1;
}
return process(str1.toCharArray(), str2.toCharArray());
}
public static int process(char[] str1, char[] str2) {
// i1是str1的匹配指针，i2是str2的匹配指针
int i1 = 0;
int i2 = 0;
// 获取str2所有字符的最长前缀和后缀
int[] next = getMaximalPrefixAndSuffix(str2);
// 匹配进程只需i1越界或者i2越界匹配都会停止（i1和i2也可能一同越界）
while (i1 < str1.length && i2 < str2.length) {
// KMP加快进程中只要三种状况
if (str1[i1] == str2[i2]) {
// 对应方位相同，str1和str2并行向后持续匹配
i1 ++;
i2 ++; // 只要匹配字符持平时i2才会往后走
} else if (i2 == 0) { // next[i2] == -1
// 对应方位不相同，可是str2的匹配指针在0方位，阐明i2跳到0方位了，意味着str1前面一整段没有方位能和str2匹配成功
// str1匹配指针向后移一位开端下一段与str2的匹配
i1 ++;
} else {
// 对应方位不相同，且str2的匹配指针不在0方位，此刻i2需求跳到最长前缀的下一位，进行下一次比较
// i2跳的这个进程便是KMP常数加快的操作
i2 = next[i2];
}
}
// 假如i2越界，那么阐明str1中匹配成功了str2，那么就回来str1中子串的首位
// 假如i1越界，那么阐明str1中没有任何一位能够与str2匹配成功，回来-1
return i2 == str2.length ? i1 - i2 : -1;
}
// 计算最大前后缀的本质便是确定str2每一位的最大前缀，预估的最大前缀在没有匹配成功时每一轮都会缩小，直到收缩到0，则表明该方位没有最大前缀
public static int[] getMaximalPrefixAndSuffix(char[] str2) {
// 假如str2中只要一个字符，那么必定是next[0]
if (str2.length == 1) {
return new int[] {-1};
}
// 假如不止一个字符，那么手动给next[0]和next[1]赋值
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
// str2的游标，从str2[2]后开端给next填值
int i = 2;
// prefix是c[i]现在最有可能的最长前缀的后一位的下标
int prefix = 0;
// 当i越界时表明next现已悉数填满
while (i < str2.length) {
if (str2[i - 1] == str2[prefix]) {
// str2[i]的前一位和str2[i]当时最有可能的最长前缀的后一位的下标相同，阐明最长前缀还能延伸，需求包括str2[prefix]
// 一同当时第i位匹配成功
next[i ++] = ++ prefix;
} else if (prefix > 0) {
// 假如str2[i]的前一位和str2[i]当时最有可能的最长前缀的后一位的下标不相同，阐明最长前缀有必要缩小，prefix需求向前跳
// prefix需求跳到c[prefix]最长前缀的后一位
// 当时第i位匹配失利，下一轮持续匹配第i位
prefix = next[prefix];
} else {
// 当prefix跳到第0位时，还和第i位匹配不上，阐明str2[i]没有最长前缀，置为0
// 一同当时第i位匹配成功
next[i ++] = 0;
}
}
return next;
}
8. 复杂度
首要证明process办法中的while循环的复杂度：
while (i1 < c1.length && i2 < c2.length) {
if (c1[i1] == c2[i2]) {
i1 ++;
i2 ++;
} else if (i2 == 0) {
i1 ++;
} else {
i2 = next[i2];
}
}
经过调查代码，咱们能够发现榜首个分支中 i1 和 i2 都增大；第二个分支中 i1 增大；第三个分支中 i2 减小。
估量while的复杂度时，咱们需求假定两个量，榜首个量是 i1，第二个量是 i1 – i2。
假定str1长度为N，那么 i1 和 i1 – i2 的最大值都是N。
咱们要看循环中的三个分支分别对这两个量的影响。
循环的榜首个分支，i1 和 i2 一同添加。因而 i1 添加，i1 – i2 不变。
循环的第二个分支，i1 添加。因而 i1 添加，i1 – i2 添加。
循环的第三个分支，i2 削减。因而 i1 不变，i1 – i2 添加。
每一次循环只会走一个分支，因而将这两个量的改变规模叠加起来，最大的起伏便是2N（走第二个分支，且都是N）。
三个分支都不会让两个量中任何一个量削减，因而循环产生的次数就和两个量改变规模的叠加绑定在了一同，两个量改变的起伏便是while循环的次数，所以整个while循环的次数不会超越2N。
因而能够证明while的时刻复杂度是线性的，为O(N)。
然后证明getMaximalPrefixAndSuffix办法的复杂度：
public static int[] getMaximalPrefixAndSuffix(char[] str2) {
if (str2.length == 1) {
return new int[] {-1};
}
int[] next = new int[str2.length];
next[0] = -1;
next[1] = 0;
int i = 2;
int prefix = 0;
while (i < str2.length) {
if (str2[i - 1] == str2[prefix]) {
next[i ++] = ++ prefix;
} else if (prefix > 0) {
prefix = next[prefix];
} else {
next[i ++] = 0;
}
}
return next;
}
估量getMaximalPrefixAndSuffix的复杂度时，咱们也需求假定两个量，榜首个量是 i，第二个量是 i – prefix。
假定str2长度为M，i 的最大值是M，i – prefix的最大值也是M。
循环的榜首个分支，i 和 prefix 一同添加。因而 i 添加，i – prefix 不变。
循环的第二个分支，prefix 削减。因而 i 不变，i – prefix 添加。
循环的第三个分支，i 添加。因而 i 添加，i – prefix 添加。
每一次循环只会走一个分支，因而将这两个量的改变规模叠加起来，最大的起伏便是2M（走第三个分支，且都是N）。
因而能够证明getMaximalPrefixAndSuffix的时刻复杂度是线性的，为O(M)。
总体时刻复杂度为：
由于M必定小于等于N，所以KMP全体时刻复杂度为O(N)。
