根据阮一峰的博客

http://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

试写算法。

使用好后缀的方法比较复杂，暂未实现。

只实现了通过坏字符的方法，事实上Boyer-Moore-Horspool算法是简化版的Boyer-Moore算法，它只使用坏字符规则。

具体代码如下：

1. class Program  
2.   {  
3.       static void Main(string[] args)  
4.       {  
5.           string source = "HERE IS A SIMPLE EXAMPLE";  
6.           string pattern = "EXAMPLE";  
7.  
8.           BoyerMoore(source.ToCharArray(), pattern.ToCharArray());  
9.       }  
10.  
11.       static int BoyerMoore(char[] source, char[] pattern)  
12.       {  
13.           Dictionary<char, int> PostionDictionary = GetPostionDictionary(pattern);  
14.           int pattern_length = pattern.Length;  
15.           int start_pointer = 0;  
16.           int end_pointer = start_pointer + pattern_length - 1;  
17.           int offset = 0;  
18.  
19.           int offset_for_print = 0;  
20.  
21.           while (end_pointer <= source.Length)  
22.           {  
23.               Console.WriteLine(source);  
24.               Console.WriteLine(new String(pattern).PadLeft(offset_for_print + pattern_length,'-'));  
25.  
26.               char[] Chars = subChars(source, start_pointer, end_pointer);  
27.               char badChar;  
28.               int badPostion;  
29.               if (checkIsEqual_badChar(pattern, Chars, out badChar, out badPostion))  
30.               {  
31.                   Console.WriteLine(start_pointer + "," + end_pointer);  
32.  
33.                   start_pointer += pattern_length;  
34.                   end_pointer = start_pointer + pattern_length - 1;  
35.                   offset_for_print += pattern_length;  
36.  
37.                   continue;  
38.               }  
39.               else 
40.               {  
41.                   if (PostionDictionary.ContainsKey(badChar))  
42.                   {  
43.                       //计算偏移量  
44.                       offset = badPostion - PostionDictionary[badChar];  
45.                   }  
46.                   else 
47.                   {  
48.                       offset = badPostion + 1;  
49.                   }  
50.                   start_pointer += offset;  
51.                   end_pointer = start_pointer + pattern_length - 1;  
52.                   offset_for_print += offset;  
53.               }  
54.           }  
55.           return 0;  
56.       }  
57.  
58.       static bool checkIsEqual_badChar(char[] pattern, char[] Chars, out char badChar, out int badPostion)  
59.       {  
60.           if (pattern.Length != Chars.Length)  
61.           {  
62.               throw new Exception("length error");  
63.           }  
64.  
65.           for (int i = pattern.Length - 1; i >= 0; i--)  
66.           {  
67.               if (pattern[i] != Chars[i])  
68.               {  
69.                   badChar = Chars[i];  
70.                   badPostion = i;  
71.                   return false;  
72.               }  
73.           }  
74.           badChar = '\0';  
75.           badPostion = -1;  
76.           return true;  
77.       }  
78.  
79.      
80.       /// <summary>  
81.       /// 根据起始位置和结束位置，给出子串  
82.       /// </summary>  
83.       /// <param name="source"></param>  
84.       /// <param name="start"></param>  
85.       /// <param name="end"></param>  
86.       /// <returns></returns>  
87.       static char[] subChars(char[] source, int start, int end)  
88.       {  
89.           char[] c = new char[end - start + 1];  
90.  
91.           for (int i = start; i <= end; i++)  
92.           {  
93.               c[i - start] = source[i];  
94.           }  
95.  
96.           return c;  
97.  
98.       }  
99.  
100.       /// <summary>  
101.       /// 生成坏字符位置表  
102.       /// </summary>  
103.       /// <param name="chars"></param>  
104.       /// <returns></returns>  
105.       static Dictionary<char, int> GetPostionDictionary(char[] chars)  
106.       {  
107.           Dictionary<char, int> d = new Dictionary<char, int>();  
108.  
109.           for (int i = 0; i < chars.Length; i++)  
110.           {  
111.               if (d.ContainsKey(chars[i]) == false)  
112.               {  
113.                   d.Add(chars[i], i);  
114.               }  
115.               else//存在则覆盖  
116.               {  
117.                   d[chars[i]] = i;  
118.               }  
119.           }  
120.           return d;  
121.       }  
122.   } 

测试数据输出图:

本文转自cnn23711151CTO博客，原文链接：http://blog.51cto.com/cnn237111/1195682 ，如需转载请自行联系原作者