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