java實(shí)現(xiàn)sunday算法示例分享

更新時(shí)間：2014年01月12日 09:16:09 作者：

Sunday算法的思想和BM算法中的壞字符思想非常類似。差別只是在于Sunday算法在匹配失敗之后，是取目標(biāo)串中當(dāng)前和Pattern字符串對(duì)應(yīng)的部分后面一個(gè)位置的字符來做壞字符匹配,寫了個(gè)小例子來實(shí)現(xiàn)以下這個(gè)算法

字符串匹配查找算法中，最著名的兩個(gè)是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。兩個(gè)算法在最壞情況下均具有線性的查找時(shí)間。但是在實(shí)用上，KMP算法并不比最簡(jiǎn)單的C庫(kù)函數(shù)strstr()快多少，而BM算法則往往比KMP算法快上3－5倍(未親身實(shí)踐)。但是BM算法還不是最快的算法，這里介紹一種比BM算法更快一些的查找算法Sunday算法。

Sunday算法的思想和BM算法中的壞字符思想非常類似。差別只是在于Sunday算法在匹配失敗之后，是取目標(biāo)串中當(dāng)前和Pattern字符串對(duì)應(yīng)的部分后面一個(gè)位置的字符來做壞字符匹配。當(dāng)發(fā)現(xiàn)匹配失敗的時(shí)候就判斷母串中當(dāng)前偏移量+Pattern字符串長(zhǎng)度+1處(假設(shè)為K位置)的字符在Pattern字符串中是否存在。如果存在，則將該位置和Pattern字符串中的該字符對(duì)齊，再?gòu)念^開始匹配；如果不存在，就將Pattern字符串向后移動(dòng)，和母串k+1處的字符對(duì)齊，再進(jìn)行匹配。重復(fù)上面的操作直到找到，或母串被找完結(jié)束。動(dòng)手寫了個(gè)小例子來實(shí)現(xiàn)以下這個(gè)算法。

在代碼中，實(shí)現(xiàn)了兩種字符串匹配算法，一種是Sunday方式，一種是普通的每次移動(dòng)一位的方式，二者的效率對(duì)比在main函數(shù)中有，都是納秒級(jí)別。算法的詳細(xì)步驟，在代碼中已經(jīng)添加了相應(yīng)的注釋。關(guān)于BM算法，下次空了再一起對(duì)照著分析。

復(fù)制代碼代碼如下:

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;

    /**
     * 匹配后的子串第一個(gè)字符位置列表
     */
    List<Integer> matchedPosList = new LinkedList<Integer>();

    /**
     * 匹配字符的Map,記錄改匹配字符串有哪些char并且每個(gè)char最后出現(xiàn)的位移
     */
    Map<Character, Integer> map = new HashMap<Character, Integer>();

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

    /**
     * Sunday匹配時(shí)，用來存儲(chǔ)Pattern中每個(gè)字符最后一次出現(xiàn)的位置，從左到右的順序
     */
    private void initMap() {
        for (int i = 0; i < pattern.length(); i++) {
            this.map.put(pattern.charAt(i), i);

}
}

    /**
     * 普通的字符串遞歸匹配，匹配失敗就前進(jìn)一位
     */
    public List<Integer> normalMatch() {
        //匹配失敗，繼續(xù)往下走
        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字符的位置為：當(dāng)前偏移量+Pattern字符串長(zhǎng)度+1
     */
    public List<Integer> sundayMatch() {
        // 如果沒有匹配成功
        if (!matchFromSpecialPos(currentPos)) {
            // 如果Text中K字符沒有在Pattern字符串中出現(xiàn)，則跳過整個(gè)Pattern字符串長(zhǎng)度
            if ((currentPos + pattern.length() + 1) < text.length()
                    && !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
                currentPos += pattern.length();
            }else {
                // 如果Text中K字符在Pattern字符串中出現(xiàn)，則將Text中K字符的位置和Pattern字符串中的最后一次出現(xiàn)K字符的位置對(duì)齊
                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 {
            // 匹配成功前進(jìn)一位然后再次匹配
            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));

}
}

您可能感興趣的文章: