java完成sunday算法示例分享

字符串婚配查找算法中，最有名的兩個是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。兩個算法在最壞情形下均具有線性的查找時光。然則在適用上，KMP算法其實不比最簡略的C庫函數strstr()快若干，而BM算軌則常常比KMP算法快上3－5倍(未親自理論)。然則BM算法還不是最快的算法，這裡引見一種比BM算法更快一些的查找算法Sunday算法。

Sunday算法的思惟和BM算法中的壞字符思惟異常相似。差異只是在於Sunday算法在婚配掉敗以後，是取目的串中以後和Pattern字符串對應的部門前面一個地位的字符來做壞字符婚配。當發明婚配掉敗的時刻就斷定母串中以後偏移量+Pattern字符串長度+1處(假定為K地位)的字符在Pattern字符串中能否存在。假如存在，則將該地位和Pattern字符串中的該字符對齊，再從頭開端婚配；假如不存在，就將Pattern字符串向後挪動，和母串k+1處的字符對齊，再停止婚配。反復下面的操作直到找到，或母串被找結束束。著手寫了個小例子來完成以下這個算法。

在代碼中，完成了兩種字符串婚配算法，一種是Sunday方法，一種是通俗的每次挪動一名的方法，兩者的效力比較在main函數中有，都是納秒級別。算法的具體步調，在代碼中曾經添加了響應的正文。關於BM算法，下次空了再一路對比著剖析。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @author Scott
 * @date 2013年12月28日
 * @description
 */
public class SundySearch {
    String text = null;
    String pattern = null;
    int currentPos = 0;

    /**
     * 婚配後的子串第一個字符地位列表
     */
    List<Integer> matchedPosList = new LinkedList<Integer>();

    /**
     * 婚配字符的Map,記載改婚配字符串有哪些char而且每一個char最初湧現的位移
     */
    Map<Character, Integer> map = new HashMap<Character, Integer>();

    public SundySearch(String text, String pattern) {
        this.text = text;
        this.pattern = pattern;
        this.initMap();
    };

    /**
     * Sunday婚配時，用來存儲Pattern中每一個字符最初一次湧現的地位，從左到右的次序
     */
    private void initMap() {
        for (int i = 0; i < pattern.length(); i++) {
            this.map.put(pattern.charAt(i), i);

        }
    }

    /**
     * 通俗的字符串遞歸婚配，婚配掉敗就進步一名
     */
    public List<Integer> normalMatch() {
        //婚配掉敗，持續往下走
        if (!matchFromSpecialPos(currentPos)) {
            currentPos += 1;

            if ((text.length() - currentPos) < pattern.length()) {
                return matchedPosList;
            }
            normalMatch();
        } else {
            //婚配勝利，記載地位
            matchedPosList.add(currentPos);
            currentPos += 1;
            normalMatch();
        }

        return matchedPosList;
    }

    /**
     * Sunday婚配，假定Text中的K字符的地位為：以後偏移量+Pattern字符串長度+1
     */
    public List<Integer> sundayMatch() {
        // 假如沒有婚配勝利
        if (!matchFromSpecialPos(currentPos)) {
            // 假如Text中K字符沒有在Pattern字符串中湧現，則跳過全部Pattern字符串長度
            if ((currentPos + pattern.length() + 1) < text.length()
                    && !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
                currentPos += pattern.length();
            }else {
                // 假如Text中K字符在Pattern字符串中湧現，則將Text中K字符的地位和Pattern字符串中的最初一次湧現K字符的地位對齊
                if ((currentPos + pattern.length() + 1) > text.length()) {
                    currentPos += 1;
                } else {
                    currentPos += pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));
                }
            }

            // 婚配完成，前往全體婚配勝利的初始位移
            if ((text.length() - currentPos) < pattern.length()) {
                return matchedPosList;
            }

            sundayMatch();
        }else {
            // 婚配勝利進步一名然後再次婚配
            matchedPosList.add(currentPos);
            currentPos += 1;
            sundayMatch();
        }
        return matchedPosList;
    }

    /**
     * 檢討從Text的指定偏移量開端的子串能否和Pattern婚配
     */
    public boolean matchFromSpecialPos(int pos) {
        if ((text.length()-pos) < pattern.length()) {
            return false;
        }

        for (int i = 0; i < pattern.length(); i++) {
            if (text.charAt(pos + i) == pattern.charAt(i)) {
                if (i == (pattern.length()-1)) {
                    return true;
                }
                continue;
            } else {
                break;
            }
        }

        return false;
    }

    public static void main(String[] args) {
        SundySearch sundySearch = new SundySearch("hello 啊啊 阿道夫 adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");

        long begin = System.nanoTime();
        System.out.println("NormalMatch:" + sundySearch.normalMatch());
        System.out.println("NormalMatch:" + (System.nanoTime() - begin));

        begin = System.nanoTime();
        System.out.println("SundayMatch:" + sundySearch.sundayMatch());
        System.out.println("SundayMatch:" + (System.nanoTime() - begin));

    }
}