九九热这里直有精品,1区二区三区在线播放,玖玖爱在线观看资源,国产aⅴ综合网,午夜福利男女,日本亚洲欧美三级,日韩无码黄色导航,内射少妇13区,中文字幕高清网

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

    Sunday算法的思想和BM算法中的壞字符思想非常類似。差別只是在于Sunday算法在匹配失敗之后，是取目標串中當前和Pattern字符串對應(yīng)的部分后面一個位置的字符來做壞字符匹配。

    當發(fā)現(xiàn)匹配失敗的時候就判斷母串中當前偏移量+Pattern字符串長度+1處(假設(shè)為K位置)的字符在Pattern字符串中是否存在。如果存在，則將該位置和Pattern字符串中的該字符對齊，再從頭開始匹配；如果不存在，就將Pattern字符串向后移動，和母串k+1處的字符對齊，再進行匹配。重復(fù)上面的操作直到找到，或母串被找完結(jié)束。

    動手寫了個小例子來實現(xiàn)以下這個算法。

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

  1 import java.util.HashMap;

  2 import java.util.LinkedList;

  3 import java.util.List;

  4 import java.util.Map;

  5 

  6 /** 

  7  * @author Scott

  8  * @date 2013年12月28日 

  9  * @description

 10  */

 11 public class SundySearch {

 12     String text = null;

 13     String pattern = null;

 14     int currentPos = 0;

 15 

 16     /**

 17      * 匹配后的子串第一個字符位置列表

 18      */

 19     List<Integer> matchedPosList = new LinkedList<Integer>();

 20     

 21     /**

 22      * 匹配字符的Map,記錄改匹配字符串有哪些char并且每個char最后出現(xiàn)的位移

 23      */

 24     Map<Character, Integer> map = new HashMap<Character, Integer>();

 25 

 26     public SundySearch(String text, String pattern) {

 27         this.text = text;

 28         this.pattern = pattern;

 29         this.initMap();

 30     };

 31 

 32     /**

 33      * Sunday匹配時，用來存儲Pattern中每個字符最后一次出現(xiàn)的位置，從左到右的順序

 34      */

 35     private void initMap() {

 36         for (int i = 0; i < pattern.length(); i++) {

 37             this.map.put(pattern.charAt(i), i);

 38 

 39         }

 40     }

 41 

 42     /**

 43      * 普通的字符串遞歸匹配，匹配失敗就前進一位

 44      */

 45     public List<Integer> normalMatch() {

 46         //匹配失敗，繼續(xù)往下走

 47         if (!matchFromSpecialPos(currentPos)) {

 48             currentPos += 1;

 49 

 50             if ((text.length() - currentPos) < pattern.length()) {

 51                 return matchedPosList;

 52             }

 53             normalMatch();

 54         } else {

 55             //匹配成功，記錄位置

 56             matchedPosList.add(currentPos);

 57             currentPos += 1;

 58             normalMatch();

 59         }

 60         

 61         return matchedPosList;

 62     }

 63 

 64     /**

 65      * Sunday匹配，假定Text中的K字符的位置為：當前偏移量+Pattern字符串長度+1

 66      */

 67     public List<Integer> sundayMatch() {

 68         // 如果沒有匹配成功

 69         if (!matchFromSpecialPos(currentPos)) {

 70             // 如果Text中K字符沒有在Pattern字符串中出現(xiàn)，則跳過整個Pattern字符串長度

 71             if ((currentPos + pattern.length() + 1) < text.length()

 72                     && !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {

 73                 currentPos += pattern.length();

 74             }else {

 75                 // 如果Text中K字符在Pattern字符串中出現(xiàn)，則將Text中K字符的位置和Pattern字符串中的最后一次出現(xiàn)K字符的位置對齊

 76                 if ((currentPos + pattern.length() + 1) > text.length()) {

 77                     currentPos += 1;

 78                 } else {

 79                     currentPos += pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));

 80                 }

 81             }

 82             

 83             // 匹配完成，返回全部匹配成功的初始位移

 84             if ((text.length() - currentPos) < pattern.length()) {

 85                 return matchedPosList;

 86             }

 87             

 88             sundayMatch();

 89         }else {

 90             // 匹配成功前進一位然后再次匹配

 91             matchedPosList.add(currentPos);

 92             currentPos += 1;

 93             sundayMatch();

 94         }

 95         return matchedPosList;

 96     }

 97 

 98     /**

 99      * 檢查從Text的指定偏移量開始的子串是否和Pattern匹配

100      */

101     public boolean matchFromSpecialPos(int pos) {

102         if ((text.length()-pos) < pattern.length()) {

103             return false;

104         }

105 

106         for (int i = 0; i < pattern.length(); i++) {

107             if (text.charAt(pos + i) == pattern.charAt(i)) {

108                 if (i == (pattern.length()-1)) {

109                     return true;

110                 }

111                 continue;

112             } else {

113                 break;

114             }

115         }

116         

117         return false;

118     }

119 

120     public static void main(String[] args) {

121         SundySearch sundySearch = new SundySearch("hello 啊啊 阿道夫 adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");

122         

123         long begin = System.nanoTime();

124         System.out.println("NormalMatch:" + sundySearch.normalMatch());

125         System.out.println("NormalMatch:" + (System.nanoTime() - begin));

126         

127         begin = System.nanoTime();

128         System.out.println("SundayMatch:" + sundySearch.sundayMatch());

129         System.out.println("SundayMatch:" + (System.nanoTime() - begin));

130 

131     }

132 }

    運行結(jié)果：

NormalMatch:[13, 17, 24]

NormalMatch:313423

SundayMatch:[13, 17, 24]

SundayMatch:36251

    使用Sunday算法要比普通的匹配算法快了10倍左右，雖然是納秒級別~因為我們匹配的內(nèi)容就那么短，內(nèi)容越長，效果就會越明顯。