BM算法笔记:
3,滑动距离函数:
为方便讨论,BM算法的关键是,对给定的模式T="t0t1…tm"定义一个从字符到正整数的映射:
dist :c->{1,2,…,m+1}
函数dist称为滑动距离函数,它给出了正文中可能出现的任意字符在模式中的位置。函数dist定义如下:
dist(c) = m-j j为c在模式中的下标,以后面的为准
dist(c) = m+1 若c不在模式中或c = tm
例如,T="pattern",则dist(p)= 6 – 0 = 6, dist(a)= 6 – 1 =5, dist(t)= 6 – 3 =3 ,dist(e)= 2, dist(r)= 1, dist(n)= 6 + 1 = 7。
4,BM算法的基本思想是:假设将主串中自位置i起往左的一个子串与模式进行从右到左的匹配过程中,若发现不匹配,则下次应从主串的i + dist(si)位置开始重新进行新一轮的匹配,其效果相当于把模式和主串向右滑过一段距离dist(si),即跳过dist(si)个字符而无需进行比较。
如这样一个例子:
从FINDINAHAYSTACKNEEDLEINA中查找NEEDLE的过程:
i j 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23
F I N D IN A H A YS T A C KN E E D L E I N A
0 5 N E E D LE
5 5 N E E D LE
11 4 N E E DL E
15 0N E E D L E
排版不是很好排,请大家见谅
第一步:i=5,j=5失败 dist(N)= 5 所以右移到5+5=10处
第二步:i=10,j=5失败 无dist(S) 所以右移到10+6 =16处
第三步:i=15,j=4失败 dist(N) = 5 所以右移到15+5 = 20处匹配成功
实例代码:
#include<iostream>
#include<stdlib.h>
#include<cstring>
using namespace std;
int dist(char *t,char ch) { //算出dist()的值
int len = strlen(t); //求子串的长度
int i = len - 1; //用于遍历子串内各字符的下标并从0开始计数
if (ch == t[i])
return len;
i--;
while (i >= 0) {
if (ch == t[i]) {
return len - 1 - i; //如果
}
else
{
i--;
}
}
return len;
}
int BM(char *s,char *t) {
int x = strlen(s);
int y = strlen(t);
int i = y - 1;
int j = y - 1;
while (j >= 0&&i<x) {
if (s[i] == t[j]) {
i--;
j--;
}
else {
i += dist(t,s[i]);//移动位置为坏字符在主串的位置+该字符在子串的值
j = y - 1; //子串回到最右边
}
}
if (j < 0) {
return i + 1;
}
return -1;
}
int main() {
char a[] = "ababcabcacbab";
char b[] = "abcac";
cout << BM(a, b) << endl;
system("pause");
return 0;
}
网友评论