?!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
字符串匹配查扄法中Q最著名的两个是KMP法QKnuth-Morris-Pratt)和BM法QBoyer-Moore)。两个算法在最坏情况下均具有线性的查找旉。但是在实用上,KMP法q不比最单的C库函数strstr()快多,而BM法则往往比KMP法快上3Q??未亲w实?。但是BM法q不是最快的法Q这里介l一U比BM法更快一些的查找法Sunday法?/strong>
Sunday法的思想和BM法中的坏字W思想非常cM。差别只是在于Sunday法在匹配失败之后,是取目标串中当前和Pattern字符串对应的部分后面一个位|的字符来做坏字W匹配?/p>
当发现匹配失败的时候就判断母串中当前偏U量+Pattern字符串长?1?假设为K位置)的字W在Pattern字符串中是否存在。如果存在,则将该位|和Pattern字符串中的该字符寚wQ再从头开始匹配;如果不存在,将Pattern字符串向后移动,和母串k+1处的字符寚wQ再q行匚w。重复上面的操作直到扑ֈQ或母串被找完结束?/p>
动手写了个小例子来实C下这个算法?/p>
在代码中Q实C两种字符串匹配算法,一U是Sunday方式Q一U是普通的每次Ud一位的方式Q二者的效率Ҏ在main函数中有Q都是纳U别。算法的详细步骤Q在代码中已l添加了相应的注释。关于BM法Q下ơ空了再一起对照着分析?/p>
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 2013q?2?8?nbsp;
9 * @description
10 */
11 public class SundySearch {
12 String text = null;
13 String pattern = null;
14 int currentPos = 0;
15
16 /**
17 * 匚w后的子串W一个字W位|列?/p>
18 */
19 List<Integer> matchedPosList = new LinkedList<Integer>();
20
21 /**
22 * 匚w字符的Map,记录改匹配字W串有哪些charq且每个char最后出现的位移
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匚wӞ用来存储Pattern中每个字W最后一ơ出现的位置Q从左到右的序
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 * 普通的字符串递归匚wQ匹配失败就前进一?/p>
44 */
45 public List<Integer> normalMatch() {
46 //匚wp|Ql往下走
47 if (!matchFromSpecialPos(currentPos)) {
48 currentPos += 1;
49
50 if ((text.length() - currentPos) < pattern.length()) {
51 return matchedPosList;
52 }
53 normalMatch();
54 } else {
55 //匚w成功Q记录位|?/p>
56 matchedPosList.add(currentPos);
57 currentPos += 1;
58 normalMatch();
59 }
60
61 return matchedPosList;
62 }
63
64 /**
65 * Sunday匚wQ假定Text中的K字符的位|ؓQ当前偏U量+Pattern字符串长?1
66 */
67 public List<Integer> sundayMatch() {
68 // 如果没有匚w成功
69 if (!matchFromSpecialPos(currentPos)) {
70 // 如果Text中K字符没有在Pattern字符串中出现Q则跌整个Pattern字符串长?/p>
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字符串中出现Q则Text中K字符的位|和Pattern字符串中的最后一ơ出现K字符的位|对?/p>
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 // 匚w完成Q返回全部匹配成功的初始位移
84 if ((text.length() - currentPos) < pattern.length()) {
85 return matchedPosList;
86 }
87
88 sundayMatch();
89 }else {
90 // 匚w成功前进一位然后再ơ匹?/p>
91 matchedPosList.add(currentPos);
92 currentPos += 1;
93 sundayMatch();
94 }
95 return matchedPosList;
96 }
97
98 /**
99 * 查从Text的指定偏U量开始的子串是否和Pattern匚w
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 啊啊 阉K?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 }
q行l果Q?/p>
NormalMatch:[13, 17, 24]
NormalMatch:313423
SundayMatch:[13, 17, 24]
SundayMatch:36251
使用Sunday法要比普通的匚w法快了10倍左叻I虽然是纳U别~因ؓ我们匚w的内容就那么短,内容长Q效果就会越明显?/p>