KMP算法(字符串匹配问题)
一、是什么？
注意，是KMP算法，不是MMP哈，我没有骂人。KMP算法是用来做字符串匹配的，除了KMP算法分，还有暴力匹配算法，也是用来做字符串匹配的。接下来先看看暴力匹配算法，你就知道为啥会出现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来遍历str1，用j来遍历str2； - 当
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算法的思想就是利用这个已知信息，不要把搜索位置移回到前面，因为前面的肯定是不匹配的。那么应该从哪儿开始比较呢？
- 可以对str2计算出一张部分匹配表：
搜索词 | A | B | C | D | A | B | D |
|---|---|---|---|---|---|---|---|
部分匹配值 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |
- 已知空格和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。上面那张部分匹配表的求值过程：
- A的前缀后缀都是空，共有元素长度为0；
- AB的前缀是A，后缀是B，共有元素长度也是0；
- ABC的前后缀共有元素长度也是0；
- 直到ABCDA，前缀和后缀共有元素长度是1；
- ABCDAB前缀和后缀共有元素长度是2；
- ABCDABD前缀和后缀共有元素长度是0。
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;
}
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
