字符串算法大揭秘：文字世界的神奇魔法
在文字的奇妙世界里，字符串算法就像一群神奇的魔法师，帮助我们在海量的文本中快速找到想要的信息。无论是在一篇长篇小说里搜索某个角色的名字，还是在代码中查找特定的函数名，字符串算法都能让这些查找工作变得高效又准确。今天，就让我们一起走进字符串算法的魔法世界，看看它们是如何施展奇妙法术的。
字符串匹配算法（暴力法）：老实的 “逐字比对者”
想象你是一个图书管理员，要在一本厚厚的书中找到某个特定的词语。最直接的方法就是从书的第一页开始，逐字逐句地查找，一个字符一个字符地比对，直到找到目标词语或者看完整个文本。这就是字符串匹配算法中的暴力法，简单直接，但有时候也有点 “笨笨” 的。
在代码世界里，暴力法的实现也是如此朴实无华。假设有一个主字符串text和一个模式字符串pattern，暴力法会从主字符串的第一个字符开始，将模式字符串与主字符串的每个位置进行逐个字符比较。如果在某个位置上，模式字符串的所有字符都与主字符串对应位置的字符相同，那么就找到了匹配。
using System;
class BruteForceStringMatch
{
public static int Search(string text, string pattern)
{
int n = text.Length;
int m = pattern.Length;
for (int i = 0; i <= n - m; i++)
{
int j;
for (j = 0; j < m; j++)
{
if (text[i + j]!= pattern[j])
{
break;
}
}
if (j == m)
{
return i;
}
}
return -1;
}
}
class Program
{
static void Main()
{
string text = "this is a test string";
string pattern = "test";
int result = BruteForceStringMatch.Search(text, pattern);
if (result!= -1)
{
Console.WriteLine($"找到了，模式字符串在主字符串的索引 {result} 处");
}
else
{
Console.WriteLine("没找到模式字符串");
}
}
}暴力法虽然简单易懂，但它的效率不高。当主字符串和模式字符串都很长时，它需要进行大量的字符比较，时间复杂度为 ，其中 是主字符串的长度， 是模式字符串的长度。就像一个勤劳但效率不高的工人，虽然努力工作，但花费的时间太多啦。
KMP 算法：聪明的 “跳跃比对者”
KMP 算法的全称是 Knuth - Morris - Pratt 算法，它就像一个聪明的侦探，在查找目标时不会盲目地逐字比对，而是会利用已经匹配的部分信息，巧妙地跳过一些不必要的比较，大大提高了查找效率。
KMP 算法的核心是构建一个部分匹配表（也叫前缀函数）。这个表记录了模式字符串中每个前缀的最长相同前缀和后缀的长度。比如，对于模式字符串ababac，它的部分匹配表为[0, 0, 1, 2, 3, 0]。在匹配过程中，如果在某个位置失配，KMP 算法不会像暴力法那样从头开始重新匹配，而是根据部分匹配表，将模式字符串向右移动合适的距离，继续进行匹配。
using System;
class KMPStringMatch
{
public static int[] ComputeLPSArray(string pattern)
{
int m = pattern.Length;
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m)
{
if (pattern[i] == pattern[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len!= 0)
{
len = lps[len - 1];
}
else
{
lps[i] = 0;
i++;
}
}
}
return lps;
}
public static int Search(string text, string pattern)
{
int n = text.Length;
int m = pattern.Length;
int[] lps = ComputeLPSArray(pattern);
int i = 0;
int j = 0;
while (i < n)
{
if (pattern[j] == text[i])
{
j++;
i++;
}
if (j == m)
{
return i - j;
}
else if (i < n && pattern[j]!= text[i])
{
if (j!= 0)
{
j = lps[j - 1];
}
else
{
i++;
}
}
}
return -1;
}
}
class Program
{
static void Main()
{
string text = "this is a test string";
string pattern = "test";
int result = KMPStringMatch.Search(text, pattern);
if (result!= -1)
{
Console.WriteLine($"找到了，模式字符串在主字符串的索引 {result} 处");
}
else
{
Console.WriteLine("没找到模式字符串");
}
}
}KMP 算法的时间复杂度为 ，在处理长文本时，比暴力法快了很多。它就像一个掌握了高效工作技巧的专家，能快速准确地完成任务。
BM 算法：机智的 “反向跳跃者”
BM 算法，即 Boyer - Moore 算法，是另一位字符串匹配的高手。它与 KMP 算法类似，但又有自己独特的技巧。BM 算法就像一个机智的探险家，在探索文本时会从模式字符串的末尾开始与主字符串进行匹配，而不是像传统方法那样从开头开始。
BM 算法利用了两个重要的规则：坏字符规则和好后缀规则。坏字符规则是指当在某个位置发现不匹配的字符（坏字符）时，根据坏字符在模式字符串中出现的位置，将模式字符串向右移动一定的距离。好后缀规则则是当部分匹配的后缀在模式字符串的其他位置也出现时，利用这个信息将模式字符串向右移动。
using System;
using System.Collections.Generic;
class BMStringMatch
{
public static int[] BadCharacterHeuristic(string pattern)
{
int m = pattern.Length;
int[] badChar = new int[256];
for (int i = 0; i < 256; i++)
{
badChar[i] = -1;
}
for (int i = 0; i < m i badcharpatterni='i;' return badchar public static int goodsuffixheuristicstring pattern int m='pattern.Length;' int suffix='new' intm int goodsuffix='new' intm 1 int i='m;' int j='m' 1 suffixi='j;' while i> 0)
{
while (j <= m && pattern[i - 1]!= pattern[j - 1])
{
if (goodSuffix[j] == 0)
{
goodSuffix[j] = j - i;
}
j = suffix[j];
}
i--;
j--;
suffix[i] = j;
}
j = suffix[0];
for (i = 0; i <= m; i++)
{
if (goodSuffix[i] == 0)
{
goodSuffix[i] = j;
}
if (i == j)
{
j = suffix[j];
}
}
return goodSuffix;
}
public static int Search(string text, string pattern)
{
int n = text.Length;
int m = pattern.Length;
int[] badChar = BadCharacterHeuristic(pattern);
int[] goodSuffix = GoodSuffixHeuristic(pattern);
int s = 0;
while (s <= n - m int j='m' - 1 while j>= 0 && pattern[j] == text[s + j])
{
j--;
}
if (j < 0)
{
return s;
}
else
{
int x = j - badChar[text[s + j]];
int y = 0;
if (j < m - 1)
{
y = goodSuffix[j + 1];
}
s += Math.Max(x, y);
}
}
return -1;
}
}
class Program
{
static void Main()
{
string text = "this is a test string";
string pattern = "test";
int result = BMStringMatch.Search(text, pattern);
if (result!= -1)
{
Console.WriteLine($"找到了，模式字符串在主字符串的索引 {result} 处");
}
else
{
Console.WriteLine("没找到模式字符串");
}
}
}BM 算法在平均情况下表现非常出色，时间复杂度通常远低于 ，但在最坏情况下，时间复杂度仍然是 。它就像一个灵活多变的运动员，能根据不同的情况快速调整策略。
Rabin - Karp 算法：神奇的 “哈希搜索者”
Rabin - Karp 算法就像一个拥有神奇魔法棒的魔法师，它利用哈希函数来快速判断模式字符串是否在主字符串中。哈希函数就像一个神奇的指纹生成器，它能将一个字符串转换为一个固定长度的数字（哈希值）。
Rabin - Karp 算法的基本思想是先计算模式字符串的哈希值，然后依次计算主字符串中每个长度与模式字符串相同的子串的哈希值。如果某个子串的哈希值与模式字符串的哈希值相同，再进行精确的字符比较，以确定是否真的匹配。
using System;
class RabinKarpStringMatch
{
private const int d = 256;
private const int q = 101;
public static int Search(string text, string pattern)
{
int n = text.Length;
int m = pattern.Length;
int h = (int)Math.Pow(d, m - 1) % q;
int p = 0;
int t = 0;
for (int i = 0; i < m; i++)
{
p = (d * p + pattern[i]) % q;
t = (d * t + text[i]) % q;
}
for (int i = 0; i <= n - m; i++)
{
if (p == t)
{
int j;
for (j = 0; j < m; j++)
{
if (text[i + j]!= pattern[j])
{
break;
}
}
if (j == m)
{
return i;
}
}
if (i < n - m)
{
t = (d * (t - text[i] * h) + text[i + m]) % q;
if (t < 0)
{
t = (t + q);
}
}
}
return -1;
}
}
class Program
{
static void Main()
{
string text = "this is a test string";
string pattern = "test";
int result = RabinKarpStringMatch.Search(text, pattern);
if (result!= -1)
{
Console.WriteLine($"找到了，模式字符串在主字符串的索引 {result} 处");
}
else
{
Console.WriteLine("没找到模式字符串");
}
}
}Rabin - Karp 算法在理想情况下，时间复杂度为 ，但在最坏情况下，时间复杂度可能会退化为 。它就像一个充满惊喜的宝藏猎人，大部分时候能快速找到宝藏，但偶尔也会遇到一些小麻烦。
总结
字符串匹配算法（暴力法）老实可靠，但效率较低；KMP 算法聪明高效，利用部分匹配信息快速查找；BM 算法机智灵活，从后向前匹配并运用坏字符和好后缀规则；Rabin - Karp 算法神奇独特，借助哈希函数快速判断。了解这些字符串算法的特点，在处理文本时就能根据不同的需求选择最合适的算法，让文本处理工作变得轻松又高效。下次遇到字符串查找问题，你就知道该请哪位 “魔法大师” 来帮忙啦！