Knuth Morris Pratt (KMP) is an algorithm, which checks the characters from left to right. When a pattern has a sub-pattern appears more than one in the sub-pattern, it uses that property to improve the time complexity, also for in the worst case.
前言 KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现,函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
KMP算法 暴力匹配算法(效率低)
用暴力匹配的思路,并假设现在str1匹配到 i 位置,子串str2匹配到 j 位置,则有: 1)如果当前字符匹配成功(即str1[i] == str2[j]),则i++,j++,继续匹配下一个字符; 2)如果失配(即str1[i]! = str2[j]),令i = i - (j - 1),j = 0。相当于每次匹配失败时,i 回溯,j 被置为0; 3)用暴力方法解决的话就会有大量的回溯,每次只移动一位,若是不匹配,移动到下一位接着判断,浪费了大量的时间。(不可行!)
KMP算法(效率高)
1)KMP是一个解决模式串在文本串是否出现过,如果出现过,最早出现的位置的经典算法; 2)Knuth-Morris-Pratt 字符串查找算法,简称为 “KMP算法”,常用于在一个文本串S内查找一个模式串P 的出现位置,这个算法由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法; 3)KMP方法算法就利用之前判断过信息,通过一个next数组,保存模式串中前后最长公共子序列的长度,每次回溯时,通过next数组找到,前面匹配过的位置,省去了大量的计算时间。
KMP分析:
KMP代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 import java.util.Arrays;public class KMP { public static void main (String[] args) { String text = "KMP是一个解决模式串在文本串是否出现过" ; String pattern = "解决模式" ; int [] next = kmpNext("ABCDABD" ); System.out.println("next=" + Arrays.toString(next)); int index = kmpMatch(text, pattern, next); System.out.println("index=" + index); } public static int kmpMatch (String text, String pattern, int [] next) { for (int i = 0 , j = 0 ; i < text.length(); i++) { while (j > 0 && text.charAt(i) != pattern.charAt(j)) { j = next[j - 1 ]; } if (text.charAt(i) == pattern.charAt(j)) { j++; } if (j == pattern.length()) { return i - j + 1 ; } } return -1 ; } public static int [] kmpNext(String pattern) { int [] next = new int [pattern.length()]; next[0 ] = 0 ; for (int i = 1 , j = 0 ; i < pattern.length(); i++) { while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) { j = next[j - 1 ]; } if (pattern.charAt(i) == pattern.charAt(j)) { j++; } next[i] = j; } return next; } public static int violenceMatch (String text, String pattern) { char [] texts = text.toCharArray(); char [] patterns = pattern.toCharArray(); int textsLen = texts.length; int patternsLen = patterns.length; int i = 0 ; int j = 0 ; while (i < textsLen && j < patternsLen) { if (texts[i] == patterns[j]) { i++; j++; } else { i = i - (j - 1 ); j = 0 ; } } if (j == patternsLen) { return i - j; } else { return -1 ; } } }
延伸 KMP 算法详解 很详尽KMP算法 kmp算法-百度百科 KMP算法图文详解 韩顺平数据结构和算法 Knuth-Morris-Pratt Algorithm 图解kmp算法-通俗易懂kmp算法
<
Algorithm Greedy
Algorithm Dynamic Programming
>