## 几种单模式匹配算法的比较 原

叶大侠

1、蛮力法:

``````int  matching(char[] src,char[] p){
int sLen = src.length;
int pLen = p.length;
for(int i=0;i<=(sLen-pLen);i++){
int j = 0; //模式P的下标
int k = i; //原串的下标
while(j<pLen){
if(src[k]!=p[j])
break;
k++;
j++;
}
if(j==pLen){
return i;
}
}
return -1;
}``````

``````static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}

char first  = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);

for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first);
}

/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j] ==
target[k]; j++, k++);

if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}``````

2、KMP算法:

``````public class KMP {
private int[] next;

/**
* 根据模式计算出next数组的各个值
*/
void initNext(char[] p) {
int i = 0, j = 0; // i是串的移动下标,j是模式的移动下标
next = new int[p.length];
next[1] = 0;
while (i < p.length) {
if (j == 0 || p[i] == p[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}

int KMPMatching(char[] src, char[] p) {
int i = 0, j = 0;
while (i < src.length && j < p.length) {
if (j == 0 || p[i] == p[j]) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == p.length)
return i - j;
return -1;
}

}``````

指针不需要回溯，效率升级为O(n+m)，要提前构造next数字，如果是源字符串不长的情况下,该方法就没什么优势了.

还有就是如果模式串p很长的话，该方法也不是很优的方法.

3、Horspool(BM的简化版)

``````private Map<Character, Integer> Table;//存储每个字符的移动表
public Horspool() {
initTable();
}

void initTable() {
Table = new HashMap<Character, Integer>();
}

void shiftTable(char[] p) {
int m = p.length;
// 初始字母表移动值为模式的长度
for (char ch = 'A'; ch <= 'z'; ch++) {
Table.put(ch, m);
}
// 模式中前m-1个字符到模式最后一个字符的长度
for (int j = 0; j < m - 1; j++)
Table.put(p[j], m - j - 1);
}

/**
* 找到的话就返回串首所在的位置，否则返回-1
*/
int HorspoolMatching(char[] p, char[] src) {
shiftTable(p);
int m = p.length;
int i = m - 1, j, k;
while (i < src.length) {
j = m - 1;
k = 0;
while (j >= 0 && src[i - k] == p[j]) {
j--;
k++;
}
// match the pattern,return the location
if (j == -1)
return i - m + 1;
else
i = Table.get(src[i]) + i;// 加上偏移值
}
return -1;
}``````

移动的距离为

if(c不包含在模式的前m-1字符中) t(c) = m  else t(c) = 模式前m-1字符中最右边的c到模式末尾的距离

4、BoyerMoore算法

``````public class BoyerMoore {

// 坏符号移动表
private Map<Character, Integer> badTable;

// 好后缀移动距离
private int[] goodSuffix;

public BoyerMoore() {
initTable();
}

void initTable() {
badTable = new HashMap<Character, Integer>();
}

void initBadTable(char[] p) {
int m = p.length;
// 初始字母表移动值为模式的长度
for (char ch = 'A'; ch <= 'Z'; ch++) {
}
// 模式中前m-1个字符到模式最后一个字符的长度
for (int j = 0; j < m - 1; j++)
badTable.put(p[j], m - j - 1);
}

// 构造好后缀移动表
void initGoodSuffix(char[] p) {
int m = p.length;
goodSuffix = new int[m - 1];
for (int i = 0; i < m - 1; i++) {
goodSuffix[i] = getSuffixLoc(p, i + 1, 0);
}
}

/**
* 获取长度为len的后缀移动距离
*/
int getSuffixLoc(char[] p, int len, int lastLoc) {
int j = getReverseLoc(p, lastLoc);
if (j == -1) {
return 0;
}
int m = p.length - 1;
int k = 1;
while (k < len && m - j >= k && p[m - k] == p[m - j - k]) {
k++;
}
if (k == len)
return j;
if (j > 0 && getReverseLoc(p, j) == -1)
return j;
return getSuffixLoc(p, len, j);
}

/**
* 从最后开始数，最后一个字符在lastLoc之后的位置
*/
int getReverseLoc(char[] p, int lastLoc) {
int m = p.length;
char lastWord = p[m - 1];
for (int i = m - 2 - lastLoc; i >= 0; i--) {
if (p[i] == lastWord)
return m - 1 - i;
}
return -1;
}

/**
* 匹配算法
*/
public int BoyerMooerMatching(char[] p, char[] src) {
initGoodSuffix(p);
int pLen = p.length, sLen = src.length;
int i = pLen - 1; // src的下标
int k = 0, j; // k为左移计数变量
int lsLen, d1, d2;
while (i < sLen) {
j = pLen - 1; // 模式p的下标
k = 0;
while (j >= 0 && p[j] == src[i - k]) {
j--;
k++;
}
if (j == -1)
return i - pLen + 1;
if (j == pLen - 1) {
i = i + badTable.get(src[i]);
} else {
lsLen = pLen - j - 1;
d1 = badTable.get(src[i]) - (lsLen);
d2 = goodSuffix[lsLen - 1];
System.out.println("d1:" + d1 + ",d2:" + d2);
i = i + (d1 > d2 ? d1 : d2);
}
}
return -1;
}

}``````

BoyerMoore把情报工作可谓做到了极致...该算法的高效让它在最差的情况下也是线性的... 如果你匹配的文本很大，强烈建议使用该算法.