|
「一、是什么？」 注意，是KMP算法，不是MMP哈，我没有骂人。KMP算法是用来做字符串匹配的，除了KMP算法，还有暴力匹配算法，也是用来做字符串匹配的。接下来先看看暴力匹配算法，你就知道为啥会出现KMP算法了。注意一点，indexOf方法，其实是用暴力匹配实现的，并不是用KMP。 「二、暴力匹配算法：」 「1. 算法思路：」 假如现有两个字符串： String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
假设现在str1匹配到i位置，str2匹配到j位置，则有： 如果当前字符匹配成功，即str1[i] == str2[j]，则i++; j++;，继续匹配下一个字符； 如果匹配不成功，即str1[i] != str2[j]，则令i = i - (j - 1); j = 0;，就是每次匹配失败，i被回溯，j置为0。
怎么理解这个过程呢？ 用i来遍历str1，j来遍历str2。一开始i=0，j=0，所以是不匹配，j就不变，i就一直后移，直到i=4的时候； 当i=4时，A和A匹配上了，此时i和j都后移，直到i=10, j=6的时候，D和空格不匹配； 此时i=i-j+1=5，j=0，即str2又从第一个字符A开始去跟str1中的第六个字符B匹配。
通过上面的描述可以发现，暴力匹配效率并不高，发现不匹配之后，回到前面第一次匹配的地方，往后移动一位，再开始匹配。每次只移动一位，会有大量回溯。 「2. 代码实现：」 public class ViolenceMatch {
public static int match(String str1, String str2) {
char[] charArr1 = str1.toCharArray();
char[] charArr2 = str2.toCharArray();
int arr1Len = charArr1.length;
int arr2Len = charArr2.length;
int i = 0; // 遍历charArr1的索引
int j = 0; // 遍历charArr2的索引
while(i<arr1Len && j<arr2Len) {
if (charArr1[i] == charArr2[j]) { // 匹配成功
i++;
j++;
} else {
i = i - j + 1;
j = 0;
}
}
if (j == arr2Len) {
return i - j;
} else {
return -1;
}
}
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
System.out.println(match(str1, str2));
}
}
「三、KMP算法：」 「1. 介绍：」 KMP算法，是一个判断字符串是否在另一个字符串中出现过的算法，如果出现过，返回最早出现的位置。和暴力匹配算法不同的是，KMP算法会用一个next数组来保存字符串中前后最长公共子序列的长度，每次回溯时，通过next找到前面匹配过的位置，这样就省了大量的时间。 「2. 案例：」 看了介绍也不知道在说什么，直接看案例吧。现有如下字符串： String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
现在要判断str1中是否包含str2，如果包含，返回str2在str1中第一次出现的位置，如果没有则返回-1。 「思路：」 当i=j=0的时候，i指向的是B，j指向的是A，不匹配； 这个时候j不动，i后移，指向的是第二个B，与j所指的A还是不匹配，i继续后移； 直到i指向了str1中第一个空格后面的那个A，才与j指向的字符匹配了； 到了上一步，A就匹配上了，接着就按同样的方式去匹配str2中的B、C…… 当匹配到str2中的D时，就发现匹配不上了，因为str1中对应的是空格； 到了上面那一步，如果是暴力匹配，那么就会让str2中的第一个字符A与str1中的第二个字符开始进行匹配，但是这样效率低。现在我们已经知道str2中的ABCDAB中str1中是存在的，KMP算法的思想就是利用这个已知信息，不要把搜索位置移回到前面，因为前面的肯定是不匹配的。那么应该从哪儿开始比较呢？
- 已知空格和D不匹配时，前面六个字符ABCDAB的匹配的，查表可知，ABCDAB对应的部分匹配值为2，因为可以按照下面的公式计算出向后移动的位数：
移动位数 = 已匹配的字符数 - 对应的部分匹配值
6 - 2 = 4，所以搜索词向后移动四位，即i向后移动四位。 - 移动四位后，能够匹配到的是AB，C与str1中的空格还是不匹配，此时AB对应的部分匹配值是0，所以移动位数为 2 - 0 = 2 位。
…… 「3. 部分匹配表怎么来的？」 一个字符串：ABCDAB，它的前缀有A，AB，ABC，ABCD，ABCDA，后缀有B，AB，DAB，CDAB，BCDAB。部分匹配值就是前缀和后缀的最长的共有元素长度。这里前缀和后缀共有元素是AB，AB的长度是2，所以值就是2。上面那张部分匹配表的求值过程： 「4. KMP算法使用步骤：」 「5. 代码实现：」 public class KmpDemo {
public static void main(String[] args) {
String str1 = "BBC ABCDAB ABCDABCDABDE";
String str2 = "ABCDABD";
System.out.println(match(str1, str2));
}
/**
* kmp获取子串在原串中第一次出现的位置
* @param str1 原串
* @param str2 子串
* @return
*/
public static int match(String str1, String str2) {
// 拿到部分匹配值表
int[] table = partMatchTable(str2);
// 遍历str1
for(int i=0, j=0; i<str1.length(); i++) {
while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
j = table[j-1];
}
if (str1.charAt(i) == str2.charAt(j)) {
j++;
} else {
}
if (j == str2.length()) {
return i - j + 1;
}
}
return -1;
}
/**
* 获取str的部分匹配表
* @param str
* @return
*/
private static int[] partMatchTable(String str) {
int[] table = new int[str.length()];
table[0] = 0;
for(int i=1, j=0; i<str.length(); i++) {
while(j > 0 && str.charAt(i) != str.charAt(j)) {
j = table[j-1];
}
if (str.charAt(i) == str.charAt(j)) {
j++;
}
table[i] = j;
}
return table;
}
}
|
