Horspool字符串匹配算法

本文要在掌握了Kmp算法的基础上阅读比较妥当

Horspool和Kmp算法有点相识，都是采用空间换时间的想法，从而达到算法运算速率的提高，运算效率也都是θ(n)，在最佳情况下，它的时间复杂度是O(n/m)，

不过，Horspool也有自己的不同点：

1、每次匹配不正确时，移动的算法和Kmp不一样

2、采用模式从右到左的匹配，一旦匹配不正确，模式串相对文本串移动table[i]个字符

先看一下该算法执行的移动过程

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到模式最后一个字符的距离                   (其他情况)

/*        * 输入： 模式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;        } 

    /*匹配过程*/            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;            }  

    /*            * 输入中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[1]    JIM_SAW_ME_IN_A_BARBERSHOP

输出：16