BM算法
BM算法也是一种字符串快速匹配算法。相对于KMP算法，BM算法往往比KMP快3-5倍。二者的区别在与匹配操作的方向不同，BM算法是将字符串左对齐，然后从右向左匹配，当匹配失败时，模式T右移的计算方法却发生了较大的变化。public class BM {
/**
* @param c 主串（源串）中的字符
* @param T 模式串（目标串）字符数组
* @return 滑动距离
*/
private static int dist(char c, char T[]) {
int n = T.length;
if (c == T) {
return n;// c出现在模式串最后一位时
}
for (int i = n; i >=1; i--) {
if (T == c)
return n - i;// i=max{i|t且0<=i<=n-2}
}
return n;// c不出现在模式中时
}
/**
* @param p_s
* @param p_t
* @return -2错误，-1匹配不到，表示t在s中位置,下标从0开始
*/
public static int index(final String p_s, final String p_t) {
if (p_s == null || p_t == null) {
return -2;
}
char[] s = p_s.toCharArray();
char[] t = p_t.toCharArray();
int slen = s.length, tlen = t.length;
if (slen < tlen) {
return -1;
}
int i = tlen, j;
while (i <= slen) {
j = tlen;
while (j > 0 && s == t) {// S与T若匹配，则进行下一组比较；反之离开循环。
i--;
j--;
}
if (0 == j){// j=0时，表示完美匹配，返回其开始匹配的位置
return i ;//如果要匹配多个，这里改为：int pos=i;i = i+tlen+1; --其中每次这个pos就是位置
}else{
//System.out.println(dist(s, t));
i = i + dist(s, t);// 把主串和模式串均向右滑动一段距离dist(s).即跳过dist(s)个字符无需比较
}
}
return -1;// 模式串与主串无法匹配
}
public static void main(String[] args) {
String s = "faabc";
String t = "abc";
System.out.println("==========:"+index(s,t));
}
}
页:
[1]