Boyer Moore算法實現(壞字符規則)

根據阮一峰的博客

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

試寫算法。

使用好后綴的方法比較復雜，暫未實現。

只實現了通過壞字符的方法，事實上Boyer-Moore-Horspool算法是簡化版的Boyer-Moore算法，它只使用壞字符規則。

具體代碼如下：

class Program  
  {  
      static void Main(string[] args)  
      {  
          string source = "HERE IS A SIMPLE EXAMPLE";  
          string pattern = "EXAMPLE";  
 
          BoyerMoore(source.ToCharArray(), pattern.ToCharArray());  
      }  
 
      static int BoyerMoore(char[] source, char[] pattern)  
      {  
          Dictionary<char, int> PostionDictionary = GetPostionDictionary(pattern);  
          int pattern_length = pattern.Length;  
          int start_pointer = 0;  
          int end_pointer = start_pointer + pattern_length - 1;  
          int offset = 0;  
 
          int offset_for_print = 0;  
 
          while (end_pointer <= source.Length)  
          {  
              Console.WriteLine(source);  
              Console.WriteLine(new String(pattern).PadLeft(offset_for_print + pattern_length,'-'));  
 
              char[] Chars = subChars(source, start_pointer, end_pointer);  
              char badChar;  
              int badPostion;  
              if (checkIsEqual_badChar(pattern, Chars, out badChar, out badPostion))  
              {  
                  Console.WriteLine(start_pointer + "," + end_pointer);  
 
                  start_pointer += pattern_length;  
                  end_pointer = start_pointer + pattern_length - 1;  
                  offset_for_print += pattern_length;  
 
                  continue;  
              }  
              else 
              {  
                  if (PostionDictionary.ContainsKey(badChar))  
                  {  
                      //計算偏移量  
                      offset = badPostion - PostionDictionary[badChar];  
                  }  
                  else 
                  {  
                      offset = badPostion + 1;  
                  }  
                  start_pointer += offset;  
                  end_pointer = start_pointer + pattern_length - 1;  
                  offset_for_print += offset;  
              }  
          }  
          return 0;  
      }  
 
      static bool checkIsEqual_badChar(char[] pattern, char[] Chars, out char badChar, out int badPostion)  
      {  
          if (pattern.Length != Chars.Length)  
          {  
              throw new Exception("length error");  
          }  
 
          for (int i = pattern.Length - 1; i >= 0; i--)  
          {  
              if (pattern[i] != Chars[i])  
              {  
                  badChar = Chars[i];  
                  badPostion = i;  
                  return false;  
              }  
          }  
          badChar = '\0';  
          badPostion = -1;  
          return true;  
      }  
 
     
      /// <summary>  
      /// 根據起始位置和結束位置，給出子串  
      /// </summary>  
      /// <param name="source"></param>  
      /// <param name="start"></param>  
      /// <param name="end"></param>  
      /// <returns></returns>  
      static char[] subChars(char[] source, int start, int end)  
      {  
          char[] c = new char[end - start + 1];  
 
          for (int i = start; i <= end; i++)  
          {  
              c[i - start] = source[i];  
          }  
 
          return c;  
 
      }  
 
      /// <summary>  
      /// 生成壞字符位置表  
      /// </summary>  
      /// <param name="chars"></param>  
      /// <returns></returns>  
      static Dictionary<char, int> GetPostionDictionary(char[] chars)  
      {  
          Dictionary<char, int> d = new Dictionary<char, int>();  
 
          for (int i = 0; i < chars.Length; i++)  
          {  
              if (d.ContainsKey(chars[i]) == false)  
              {  
                  d.Add(chars[i], i);  
              }  
              else//存在則覆蓋  
              {  
                  d[chars[i]] = i;  
              }  
          }  
          return d;  
      }  
  } 

測試數據輸出圖: