C#，字符串匹配（模式搜索）Boyer Moore算法的源代码

Boyer Moore 算法是字符串匹配（模式搜索）的主要高效算法之一。

Boyer-Moore（BM）算法被认为最高效的字符串搜索算法，它由Bob Boyer和J Strother Moore于1977年设计实现。通常情况下，Boyer Moore 算法比KMP算法快3-5倍。

BM算法的精华就在于BM(text, pattern),也就是BM算法当不匹配的时候一次性可以跳过不止一个字符。即它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。即它充分利用待搜索字符串的一些特征，加快了搜索的步骤。

BM算法实际上包含两个并行的算法（也就是两个启发策略）：坏字符算法（bad-character shift）和好后缀算法（good-suffix shift）。这两种算法的目的就是让模式串每次向右移动尽可能大的距离（即上面的BM()尽可能大）。

本代码运行效果：

源代码：

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?/// <summary>
?? ?/// 字符串匹配算法（模式搜索）Boyer Moore 算法
?? ?/// </summary>
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?/// <summary>
?? ??? ?/// “坏字符”限制（数组大小）
?? ??? ?/// 处理中文，这个要大大增加！！！！
?? ??? ?/// </summary>
?? ??? ?//private static int NO_OF_CHARS = 256;

?? ??? ?/// <summary>
?? ??? ?/// “坏字符启发式”的预处理函数
?? ??? ?/// The preprocessing function for bad character heuristic
?? ??? ?/// </summary>
?? ??? ?/// <param name="patternCharArray"></param>
?? ??? ?/// <param name="badcharArray"></param>
?? ??? ?public static void Bad_Char_Heuristic(char[] patternCharArray, out int[] badcharArray)
?? ??? ?{
?? ??? ??? ?badcharArray = new int[ALPHA_CODE_MAX];
?? ??? ??? ?for (int i = 0; i < ALPHA_CODE_MAX; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?badcharArray[i] = -1;
?? ??? ??? ?}

?? ??? ??? ?for (int i = 0; i < patternCharArray.Length; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?badcharArray[(int)patternCharArray[i]] = i;
?? ??? ??? ?}
?? ??? ?}

?? ??? ?/// <summary>
?? ??? ?/// 使用了“坏字符启发式”的
?? ??? ?/// 字符串匹配算法（模式搜索）Boyer Moore 算法
?? ??? ?/// A pattern searching function that uses Bad
?? ??? ?/// Character Heuristic of Boyer Moore Algorithm
?? ??? ?/// </summary>
?? ??? ?/// <param name="text"></param>
?? ??? ?/// <param name="pattern"></param>
?? ??? ?public static List<int> Boyer_Moore_Search(string text, string pattern)
?? ??? ?{
?? ??? ??? ?int m = pattern.Length;
?? ??? ??? ?int n = text.Length;

?? ??? ??? ?List<int> matchs = new List<int>();

?? ??? ??? ?Bad_Char_Heuristic(pattern.ToCharArray(), out int[] badchar);
?? ??? ??? ?
?? ??? ??? ?int s = 0;
?? ??? ??? ?while (s <= (n - m))
?? ??? ??? ?{
?? ??? ??? ??? ?int j = m - 1;
?? ??? ??? ??? ?while (j >= 0 && pattern[j] == text[s + j])
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?j--;
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 如果匹配串出现在当前位置
?? ??? ??? ??? ?if (j < 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?matchs.Add(s);

?? ??? ??? ??? ??? ?// 改变模式，使下一个文本中的字符与最后一个对齐它在匹配串中的出现。
?? ??? ??? ??? ??? ?// 条件s + m < n是，当匹配串出现在末端时的情况。
?? ??? ??? ??? ??? ?s += (s + m < n) ? m - badchar[text[s + m]] : 1;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?// 修改匹配数值，让“坏字符”在文本中与最后一次出现的是匹配串。
?? ??? ??? ??? ??? ?// max函数用于确保我们得到积极的转变。
?? ??? ??? ??? ??? ?// 如果最后一次坏字母在匹配串中的出现位于当前角色的右侧。
?? ??? ??? ??? ??? ?s += Math.Max(1, j - badchar[text[s + j]]);
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return matchs;
?? ??? ?}
?? ?}
}
?

-----------------------------------------------------------------------

POWER BY TRUFFER.CN

using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
?? ?/// <summary>
?? ?/// 字符串匹配算法（模式搜索）Boyer Moore 算法
?? ?/// </summary>
?? ?public static partial class PatternSearch
?? ?{
?? ??? ?/// <summary>
?? ??? ?/// “坏字符”限制（数组大小）
?? ??? ?/// 处理中文，这个要大大增加！！！！
?? ??? ?/// </summary>
?? ??? ?//private static int NO_OF_CHARS = 256;

?? ??? ?/// <summary>
?? ??? ?/// “坏字符启发式”的预处理函数
?? ??? ?/// The preprocessing function for bad character heuristic
?? ??? ?/// </summary>
?? ??? ?/// <param name="patternCharArray"></param>
?? ??? ?/// <param name="badcharArray"></param>
?? ??? ?public static void Bad_Char_Heuristic(char[] patternCharArray, out int[] badcharArray)
?? ??? ?{
?? ??? ??? ?badcharArray = new int[ALPHA_CODE_MAX];
?? ??? ??? ?for (int i = 0; i < ALPHA_CODE_MAX; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?badcharArray[i] = -1;
?? ??? ??? ?}

?? ??? ??? ?for (int i = 0; i < patternCharArray.Length; i++)
?? ??? ??? ?{
?? ??? ??? ??? ?badcharArray[(int)patternCharArray[i]] = i;
?? ??? ??? ?}
?? ??? ?}

?? ??? ?/// <summary>
?? ??? ?/// 使用了“坏字符启发式”的
?? ??? ?/// 字符串匹配算法（模式搜索）Boyer Moore 算法
?? ??? ?/// A pattern searching function that uses Bad
?? ??? ?/// Character Heuristic of Boyer Moore Algorithm
?? ??? ?/// </summary>
?? ??? ?/// <param name="text"></param>
?? ??? ?/// <param name="pattern"></param>
?? ??? ?public static List<int> Boyer_Moore_Search(string text, string pattern)
?? ??? ?{
?? ??? ??? ?int m = pattern.Length;
?? ??? ??? ?int n = text.Length;

?? ??? ??? ?List<int> matchs = new List<int>();

?? ??? ??? ?Bad_Char_Heuristic(pattern.ToCharArray(), out int[] badchar);
?? ??? ??? ?
?? ??? ??? ?int s = 0;
?? ??? ??? ?while (s <= (n - m))
?? ??? ??? ?{
?? ??? ??? ??? ?int j = m - 1;
?? ??? ??? ??? ?while (j >= 0 && pattern[j] == text[s + j])
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?j--;
?? ??? ??? ??? ?}

?? ??? ??? ??? ?// 如果匹配串出现在当前位置
?? ??? ??? ??? ?if (j < 0)
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?matchs.Add(s);

?? ??? ??? ??? ??? ?// 改变模式，使下一个文本中的字符与最后一个对齐它在匹配串中的出现。
?? ??? ??? ??? ??? ?// 条件s + m < n是，当匹配串出现在末端时的情况。
?? ??? ??? ??? ??? ?s += (s + m < n) ? m - badchar[text[s + m]] : 1;
?? ??? ??? ??? ?}
?? ??? ??? ??? ?else
?? ??? ??? ??? ?{
?? ??? ??? ??? ??? ?// 修改匹配数值，让“坏字符”在文本中与最后一次出现的是匹配串。
?? ??? ??? ??? ??? ?// max函数用于确保我们得到积极的转变。
?? ??? ??? ??? ??? ?// 如果最后一次坏字母在匹配串中的出现位于当前角色的右侧。
?? ??? ??? ??? ??? ?s += Math.Max(1, j - badchar[text[s + j]]);
?? ??? ??? ??? ?}
?? ??? ??? ?}

?? ??? ??? ?return matchs;
?? ??? ?}
?? ?}
}