Horspool字符串匹配算法
本文要在掌握了Kmp算法的基础上阅读比较妥当
Horspool和Kmp算法有点相识，都是采用空间换时间的想法，从而达到算法运算速率的提高，运算效率也都是θ(n)
不过，Horspool也有自己的不同点：
1、每次匹配不正确时，移动的算法和Kmp不一样
2、采用模式从右到左的匹配，一旦匹配不正确，模式串相对文本串移动table[i]个字符
先看一下该算法执行的移动过程
字符c A B C D E F ... R ... Z -
移动距离 4 2 6 6 1 6 6 3 6 6 6
J I M _ S A W _ M E _ I N _ A _ B A R B E R S H O P
BAR B E R B A R B E R
B A R B E R B A R B E R
B A R B E R B A R B E R
接下类我们看一下他的移动数据数组是怎么求的
t(c) = {模式的长度m 如果c不包括在模式的前m-1个字符中)
模式前m-1个字符中最右边的c到模式最后一个字符的距离 (其他情况)
[java]
/*
* 输入： 模式p[0..m-1]以及一个可能出现字符的字母表 输出: 以字母表中字符为索引的数组table[0..size-1]
*/
public int[] ShiftTable(char p[], int m)
{
int[] table = new int[150];
for (int i = 0; i < table.length; i++)
{
table[i] = m ;
}
for (int i = 0; i < m - 1; i++)
{
table[p[i]] = m - 1 - i;
}
return table;
}
匹配过程
[java]
/*匹配过程*/
public int HorspoolMatching(char p[], int m, char[] t, int n,int table[])
{
int i = m - 1;
// 匹配模式字符串字符个数
int k = 0;
while (i < n)
{
k = 0;
while (k < m && p[m - 1 - k] == t[i - k])
k++;
//当匹配个数等于模式串个数
if (k == m) { return i - m + 1; }
else i = i + table[t[i]];
}
return -1;
}
测试程序
[java]
/*
* 输入中args[0]为模式串 输出中args[1]为文本串
*/
public static void main(String[] args)
{
Hoospool h = new Hoospool();
// 取得模式串以及长度
char[] p = args[0].toCharArray();
int m = p.length;
// 取得文本串以及长度
char[] t = args[1].toCharArray();
int n = t.length;
int[] table = h.ShiftTable(p, p.length);
//找到返回的下标值
int index = h.HorspoolMatching(p, m, t, n, table);
System.out.println(index);
}
args[0] BARBER
args[1] JIM_SAW_ME_IN_A_BARBERSHOP
输出：16
补充：综合编程 , 其他综合 ,
