参考：字符串匹配的KMP算法 - 阮一峰的网络日志

           经典算法--Aho-Corasick automaton — carlos9310

           KMP算法：线性时间O(n)字符串匹配算法_qingdujun的博客-CSDN博客

目录

一、KMP next数组（失配表）程序生成算法

二、打印计算过程

三、重点理解

第1步

第2步

Next数组如何实现这种逻辑呢？

继续第3步

四、KMP算法

五、KMP算法-java版

一、KMP next数组（失配表）程序生成算法

# 由模式串生成的部分匹配表，其存储的是前缀尾部 的位置。有前缀尾部 = next(后缀尾部)， # 当后缀之后q不匹配时，通过查询部分匹配表，确定前缀尾部的位置k,然后将前缀滑动过来与后缀对齐，继续后续匹配工作 # 程序法计算部分匹配表 def partialMatchTable(p): pLen = len(p) Next = [0] k = 0 # 模式串nP的下标 for q in range(1,pLen): # 文本串nT的下标 while k > 0 and p[k] != p[q]: k = Next[k-1] if p[k] == p[q]: k += 1 Next.append(k) return Next p='ababaca' partialMatchTable(p)

上面算法（python3）来自第二个参考文档，一直不理解：为何不匹配时k=Next[k-1]？

因一直理解next代表的是当前位置逆序最大匹配字符数，是一个匹配长度，为何直接可以作为字符串下标来使用（p[k] != p[q]）？

 后来看了第一个参考文档，将上面相应的值打印出来后，慢慢理解了，这篇文章就是写这个理解过程。

二、打印计算过程

输入p=ababaca，打印出next为：0012301，下面会竖排对齐展示，方便理解。

讯享网k > 0 and p[k] != p[q]（下称条件1）不满足 p[k] == p[q]（下称条件2）不满足

三、重点理解

重点理解上图红色的3步，即匹配失败时的跳表计算，下面图解1/2/3步。

*下面第N位无特殊说明，均表示 查找文本的第N位（也就是源文本的第N位，=下标+1）。

第1步

Next    ：00123

源文本：ababa[c]a

查    找：   aba[b]aca

讯享网

Next    ：   00123

此时源文本第6位c和该批次连续匹配的b不相符，用已匹配的最后一位（a字符）对应的Next值（1），其对应的字符b来匹配：

第2步

Next    ：00123

源文本：ababa[c]a

查    找：        a[b]abaca

Next    ：        00123

为何可以从第4位（第1步不匹配的b）直接跳到第2位？而不是从开头右移一位，用第1位的a来比较第4位的b？如下图

源文本：aba[b]aca

查    找：      [a]babaca

可以肉眼看到右移一位，第1位的a和源文本第4位的b是不匹配的，需要再右移一位，第1位的a和源文本第5位的a，此时才匹配。所以程序要自动右移2位才可以实现高效匹配。

Next数组如何实现这种逻辑呢？

这就要再理解下Next数组的含义，我的理解是：Next数组的值对应该位置（含）逆序最大匹配字符数。

1-但是和谁匹配呢？是和起始位置开始的连续字符匹配，也就是说Next数组的值是可以作为下标使用的（因为起始位置下标为0），这就解释了为何可以作为下标使用；

2-但为何可以直接跳表呢？是因为Next数组的值还有一层含义：上一个可替换的位置（第1步的图）：

Next    ：00123

源文本：ababa[c]a

查    找：   aba[b]aca

Next    ：   00123

第4位b查找不匹配，第3位a是匹配的，只是其后续的字符无法继续匹配，所以要找到a对应的可替换的上一个位置1（第1位），此时1其代表的第3位的a逆序和最开头的第1位的a正序开始的字符相同，且连续长度为1；

也就是下一次比较时，第1位的a的下一个字符b（第2位，下标=1）可以直接和源文本第6位的c进行比较（第2步的图）：

Next    ：00123

源文本：ababa[c]a

查    找：        a[b]abaca

Next    ：        00123

这样就实现了跳表：之前已经匹配过的字符无需再次匹配，可以直接复用匹配结果，用上一个可替换的位置来进行替换；计算上正好下一个字符下标1=Next值（第1位），故可以直接使用。

最后再看下：

while k > 0 and p[k] != p[q]: k = Next[k-1] if p[k] == p[q]: k += 1 

就可以理解 k = Next[k-1] 跳表及  p[k] != p[q] 直接比较了。

总结下， Next数组代表的是当前下标字符（含）逆序，匹配从0开始的文本的字符数，其值可作为下标直接使用，同时具有替换作用。

继续第3步

当前源文本第6位c和第2位b不匹配，查找上一位已匹配的a，对应的Next数组值0，即之前没有可替换位置，从头开始匹配：

Next    ：00123

源文本：ababa[c]a

查    找：          [a]babaca

Next    ：          00123

最终跳出while循环。

四、KMP算法

讯享网def partialMatchTable(p): pLen = len(p) next = [0] k = 0 for q in range(1,pLen): while k > 0 and p[k] != p[q]: k = next[k-1] if p[k] == p[q]: k += 1 next.append(k) return next def kmp(str, p): sLen = len(str) pLen = len(p) if sLen < pLen: return -2 next = partialMatchTable(p) k = 0 for q in range(0, sLen): while k > 0 and str[q] != p[k]: k = next[k - 1] if str[q] == p[k]: k = k + 1 if k == pLen: return q - pLen + 1 return -1 # Press the green button in the gutter to run the script. if __name__ == '__main__': T = 'Press the green button in the gutter to run the script.' for start in range(0, len(T) - 1): for i in range(start + 1, len(T)): P = T[start:i] try: findIndex = kmp(T, P) except Exception as e: print("exception:" + P) print(e) break endIndex = findIndex + len(P) if T[findIndex:endIndex] != P: print("error:" + P) print("SUCCESS")

python3脚本，只返回第一次匹配的下标位置（如需多个，可返回数组）；如没有找到返回<0。

五、KMP算法-java版

public class KmpAlgorithm { / * 原始模式串文本 */ private char[] pattern; / * 失配表，按照下标跳转 */ private int[] next; / * 返回失配表 copy * * @return */ public int[] getNextCopy() { if (next == null) { return null; } if (next.length == 0) { return new int[0]; } int[] copy = new int[next.length]; System.arraycopy(next, 0, copy, 0, next.length); return copy; } / * next失配表：next值表示的是当前下标字符不匹配时，可以使用该值-1的下标继续匹配。 * 比如模式串： * abcabdab * 00012012 * 要匹配的文本： * <p> * 待匹配：abca[d]eeeeeeeeeee * 模式串：abca[b]dab * <p> * 此时模式串[b]不匹配，其对应的next值是2-1=1，也就是转成： * <p> * 待匹配：abca[d]eeeeeeeeeee * 模式串： a[b]cabdab * <p> * 此时直接跳转到第二位（下标1），这样可以省略一步一步的右移，节省了2步。发现仍不匹配，再照此跳转： * <p> * 待匹配：abca[d]eeeeeeeeeee * 模式串： [a]bcabdab * <p> * 发现仍不匹配，而此时模式串已是起始位置，故右移一位继续进行匹配： * <p> * 待匹配：abcad[e]eeeeeeeeee * 模式串： [a]bcabdab * <p> * 直到匹配完成，如果有匹配则记录下起始位置后续返回即可。 */ public void generateNext(String originPattern) { assert originPattern != null && originPattern.length() > 0; pattern = originPattern.toCharArray(); next = new int[pattern.length]; / * 生成失配表 */ next[0] = 0; for (int i = 1; i < pattern.length; i++) { int nextIndex = next[i - 1]; while (true) { if (pattern[i] == pattern[nextIndex]) { next[i] = nextIndex + 1; break; } else { / * 当前不匹配，使用前一个字符对应失配表的值进行跳转匹配，比如前面next值都已计算，现在需计算第10位（下标9）d的next值： * abcabcabc[d]eee * 000 * abcabc[a]bcdeee * 跳转 * abcabcabc[d]eee * abc[a]bcabcdeee * 跳转 * abcabcabc[d]eee * [a]bcabcabcdeee * 已经到起始位置仍不匹配，得到0，移到下一位e开始继续计算。 */ if (nextIndex == 0) { next[i] = 0; break; } nextIndex = next[nextIndex - 1]; } } } } / * 在text中查找pattern，看下有多少完全匹配的 * * @param text * @return 匹配的text下标，-1标识没有匹配 */ public int matchFirst(String text) { for (int i = 0; i < text.length(); ) { int patternIndex = 0; while (i < text.length()) { if (text.charAt(i) == pattern[patternIndex]) { i++; patternIndex++; if (patternIndex == pattern.length) { //完全匹配 return i - pattern.length; } } else { if (patternIndex == 0) { //已经回溯到起始位置仍不匹配，说明该i位置没有匹配，向后移动一位 i++; break; } //回溯 patternIndex = next[patternIndex - 1]; } } } return -1; } / * 在text中查找pattern，看下有多少完全匹配的，只匹配部分结果，并非全部位置结果 * * @param text * @return 匹配的text下标，多个以数组形式返回 */ public Integer[] matchSome(String text) { List<Integer> findStartIndexes = new ArrayList<>(); int patternIndex = 0; for (int i = 0; i < text.length(); i++) { while (patternIndex > 0 && text.charAt(i) != pattern[patternIndex]) { patternIndex = next[patternIndex - 1]; } if (text.charAt(i) == pattern[patternIndex]) { patternIndex++; } if (patternIndex == pattern.length) { //完全匹配 findStartIndexes.add(i + 1 - pattern.length); patternIndex = 0; } } return findStartIndexes.toArray(new Integer[findStartIndexes.size()]); } public Integer[] matchAll(String text) { Set<Integer> findStartIndexes = new HashSet<>(); LinkedList<Integer> skipIndex = new LinkedList<>(); skipIndex.add(0); int patternIndex; while (!skipIndex.isEmpty()) { int startIndex = skipIndex.remove(0); patternIndex = 0; for (int i = startIndex; i < text.length(); i++) { while (patternIndex > 0 && text.charAt(i) != pattern[patternIndex]) { patternIndex = next[patternIndex - 1]; } if (text.charAt(i) == pattern[patternIndex]) { if (startIndex != i && !skipIndex.contains(i)) skipIndex.add(i); patternIndex++; } if (patternIndex == pattern.length) { //完全匹配 findStartIndexes.add(i + 1 - pattern.length); patternIndex = 0; skipIndex.remove((Object) (i + 1 - pattern.length)); } } } return findStartIndexes.toArray(new Integer[findStartIndexes.size()]); } } 

附带junit4测试类：

讯享网import org.junit.Test; import java.util.*; import java.util.function.Function; import static org.junit.Assert.assertArrayEquals; import static org.junit.Assert.assertEquals; public class KmpAlgorithmTest { public static final Random random = new Random(System.currentTimeMillis()); @Test public void testGenerate() { KmpAlgorithm kmp = new KmpAlgorithm(); kmp.generateNext("abababcabc"); assertEquals("[0, 0, 1, 2, 3, 4, 0, 1, 2, 0]", Arrays.toString(kmp.getNextCopy())); kmp.generateNext("aaaaa"); assertEquals("[0, 1, 2, 3, 4]", Arrays.toString(kmp.getNextCopy())); kmp.generateNext("abcdefg"); assertEquals("[0, 0, 0, 0, 0, 0, 0]", Arrays.toString(kmp.getNextCopy())); } @Test public void testMathFirst() { String pattern = "babba"; KmpAlgorithm kmp = new KmpAlgorithm(); kmp.generateNext(pattern); assertEquals(0, kmp.matchFirst(pattern)); assertEquals(0, kmp.matchFirst(pattern + pattern)); assertEquals(-1, kmp.matchFirst("")); assertEquals(1, kmp.matchFirst("$" + pattern)); assertEquals(2, kmp.matchFirst("$$" + pattern)); assertEquals(3, kmp.matchFirst("$$$" + pattern)); assertEquals(3, kmp.matchFirst("$$$" + pattern + "$$$")); } @Test public void testMatchSome() { KmpAlgorithm kmp = new KmpAlgorithm(); testLoop(kmp, kmp::matchSome, false); } @Test public void testMatchAll() { KmpAlgorithm kmp = new KmpAlgorithm(); testLoop(kmp, kmp::matchAll, true); } private void testLoop(KmpAlgorithm kmp, Function<String, Integer[]> func, boolean checkAll) { String pattern = generateData(new Character[]{'a', 'b'}, 5); // pattern = "aaaaa"; System.out.println("pattern:" + pattern); kmp.generateNext(pattern); System.out.println(Arrays.toString(kmp.getNextCopy())); System.out.println("BEGIN..."); Set<Character> seedSet = getSeed(pattern); for (int i = 1; i < 101; i++) { String text = generateData(seedSet.toArray(new Character[0]), i); System.out.print("text:" + text + "\t"); Integer[] result = func.apply(text); //check-1 for (int j = 0; j < result.length; j++) { int patterIndex = 0; for (int k = result[j]; k < result[j] + pattern.length(); k++) { if (pattern.charAt(patterIndex++) != text.charAt(k)) { System.out.println("matched indexes error:" + j + ", all:" + Arrays.toString(result)); return; } } } //check-2 if(checkAll) { Integer[] bmatches = bruteForceMatch(pattern, text); Arrays.sort(bmatches); Arrays.sort(result); assertArrayEquals(bmatches, result); } System.out.print(Arrays.toString(result)); System.out.println(); } System.out.println("END"); } private String generateData(Character[] seed, int size) { StringBuilder bld = new StringBuilder(size); for (int i = 0; i < size; i++) { bld.append(seed[random.nextInt(seed.length)]); } return bld.toString(); } private Set<Character> getSeed(String pattern) { Set<Character> seedSet = new HashSet<>(); for (int i = 0; i < pattern.length(); i++) { seedSet.add(pattern.charAt(i)); } return seedSet; } / * 暴力查找 * * @param pattern * @param text * @return */ private Integer[] bruteForceMatch(String pattern, String text) { List<Integer> matchIndex = new ArrayList<>(); for (int i = 0; i < text.length(); i++) { int index1 = i; int j = 0; for (; index1 < text.length() && j < pattern.length(); j++) { if (text.charAt(index1) == pattern.charAt(j)) { index1++; } else { break; } } if (j == pattern.length()) { //match matchIndex.add(i); } } return matchIndex.toArray(new Integer[0]); } }