当前位置 博文首页 > Aaron_Yang：字符串匹配——BF算法与KMP算法（java详解版）
BF算法：
?????BF算法即暴力(Brute Force)算法，是普通的模式匹配算法。BF算法的思想：将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。
??? ?? BF算法就是依次的进行比较，若比较失败，则重新比较下一个。
package com.southwind;
public class BF {
//暴力匹配
public static void main(String[] args)
{
String str1="abcdabeabcdabd";
String str2="abcdabd";
int index = violenceMatch(str1,str2);
if(index!=-1)
System.out.println("匹配成功：index="+index);
else
System.out.println("匹配失败");
}
private static int violenceMatch(String str1,String str2)
{
char []a1 = str1.toCharArray();
char []a2 = str2.toCharArray();
int s1_len = a1.length;
int s2_len = a2.length;
int i = 0;// i的索引指向s1
int j = 0;// j的索引指向s2
while(i<s1_len && j<s2_len)
{
//进行判断
if(a1[i]==a2[j])
{
i++;
j++;
}
else
{
//没有匹配成功
//例如 i =2时开始匹配，i=7，j=5匹配失败 则 i从3开始
i = i-j+1;
j = 0;
}
}
//判断是否匹配成功（结果是按数组0开始计算）
if(j == s2_len)
return i-j;
else
return -1;
}
}
结果：
KMP算法：
?????KMP算法是一种改进的字符串匹配算法,其关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的
KMP算法核心：
package com.southwind;
public class KMP {
public static void main(String[] args) {
String s1 = "abcdabeabcdabd";
String s2 = "abcdabd";
int result = kmp(s1, s2);
System.out.println(result);
}
public static int kmp(String str1, String str2) {
char a[] = str1.toCharArray();
char b[] = str2.toCharArray();
int a_len = a.length;
int b_len = b.length;
int next[] = {-1, 0, 0, 0, 0, 1, 2};
//在串s 和串t中 分别设置比较的下标 i和j
int i = 0, j = 0;
//循环直到所有的字符均比较完
while (i < a_len && j < b_len) {
if (j == -1 || a[i] == b[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == b_len)
return (i - j);
else
return -1;
}
}
结果：
