一、应用场景-字符串匹配问题 1) 有一个字符串 str1= "BBC ABCDAB ABCDABCDABDE ",和一个子串 str2="ABCDABD " 2) 现在要判断 str1 是否含有 str2 , 如果存在,就返回第一次出现的位置 , 如果没有,则返回 -1
二、解决方式-暴力匹配
如果用暴力匹配的思路,并假设现在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) 用暴力方法解决的话就会有大量的 回溯 ,每次只移动 一位 ,若是不匹配,移动到下一位接着判断,浪费了大量的时间。 ( 不可行 !) public static int violenceMatch(String source, String target) {
int i = 0, j = 0;
char[] s1 = source.toCharArray();
char[] s2 = target.toCharArray();
//任意一个索引越界了就结束 一般i越界了有可能没找到,j越界了是找到了
while (i < source.length() && j < target.length()) {
count++;
//第一个字符匹配成功,接着往下面匹配
if (s1[i] == s2[j]) {
i++;
j++;
} else {
//匹配不成功,从下一个位置重新开始匹配
i = i - j + 1;
j = 0;
}
//j指向了目标字符串的最后,匹配成功了
if (j == target.length()) return i - j;
}
return -1;
}
三、解决方式-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算法利用next数组动态地计算每次匹配后移的位数。next数组利用目标字符串在匹配前就已得出。
3.1 前缀与后缀 3.2 next数组与部分匹配值: 3.3 举例
假如我们已经匹配到了这里,可以看到下一个字符不匹配。
如果按照暴力方法,下一次匹配的位置应该是最开始匹配位置的后一位:
利用KMP算法,计算出下一次后移的位数是 4 位:
(已匹配字符数(6)- 最后一个已匹配字符的部分匹配值(2))
四、KMP的代码演示1、首先是获取next数组,这个是网上的版本,我不理解。我在主程序中用别的思路实现了同样的结果
//获取next数组的网上版本,我看不懂
public static int[] Next1(String s) {
int[] next = new int[s.length()];
next[0] = 0;//第一个元素无论如何都是0,不跟自己匹配
//索引后移
for (int i = 1, k = 0; i < s.length(); i++) {
while (k > 0 && s.charAt(k) != s.charAt(i)) k = next[k - 1];//
if (s.charAt(k) == s.charAt(i)) k++;//如果某次匹配到了,就让匹配长度+1
next[i] = k;//不论每次是否匹配到都把k赋给next的对应元素,也就是匹配长度
}
return next;
}
2.主程序
注:next数组的思路:
1. i指向字符串首位,j指向字符串首位的后一位。j 不断后移,直到遇到和首位相同的字符时 i、j同时后移,这时同时记录匹配长度到next数组中。
2. 一旦又遇到了不同的字符,i 就回到字符串首位,而 j 始终后移。清空 匹配长度变量,等待下一次匹配。
3.如果又匹配成功了,就重复类似于 1 的操作(i、j同时后移)。直到 j 指到了字符串末尾。
public static Integer count=0;//匹配次数计数,对比两种方法
public static int KMPMatch(String source,String target){
//1、获得next数组,这是kmp算法的关键,这样我们才能决定下次从哪里开始匹配
int[] next = new int[target.length()];
int matchedLength = 0, i = 0, j = 1;
next[0] = 0;//第一个元素无论如何都是0,不跟自己匹配
//i指向字符首位,j后移。
while (j < target.length()) {
//如果 i 与 j 所指字符匹配成功,就同时后移,同时记录匹配的字符长度
if (target.charAt(i) == target.charAt(j)) {
next[j] = ++matchedLength;
i++;
//否则就把 i 移到首位,匹配长度清零
} else {
i = 0;
matchedLength = 0;
}
//j始终向后遍历
j++;
}
//2、真正的匹配过程
int k = 0, l = 0;//k指向源字符串,l指向目标字符串
int matched=0;
char[] s1 = source.toCharArray();
char[] s2 = target.toCharArray();
//任意一个索引越界了就结束 一般i越界了有可能没找到,j越界了是找到了
while (k < source.length() && l < target.length()) {
count++;
//第一个字符匹配成功,接着往下面匹配
if (s1[k] == s2[l]) {
k++;
l++;
matched++;
} else {
//匹配不成功,从后面位置重新开始匹配,这个位置经过了kmp算法的优化
if(matched>=1) k=k-l+matched-next[matched-1];//字符长度不为0,那就根据算法选择下次开始比较的位置
else k=k-l+1;//字符长度为0,那就跟暴力方法一样回到原来位置的下一位
l = 0;
matched=0;
}
//l指向了目标字符串的最后,匹配成功了
if (l == target.length()) return k - l;
}
return -1;
}
五、最终对比
@Test
public void testViolenceMatch() {
String source = "BBC ABCDAB ABCDABCDABDE";
String target = "ABCDABD";
System.out.println(solution.violenceMatch(source, target));
System.out.println("匹配次数:"+solution.count);
}
15
匹配次数:36
@Test
public void testKMPMatch() {
String source = "BBC ABCDAB ABCDABCDABDE";
String target = "ABCDABD";
System.out.println(solution.KMPMatch(source,target));
System.out.println("匹配次数:"+solution.count);
}
15
匹配次数:29



