什么是最有效（时间最短）的字符串搜索方法？（C＃）

Question

我发现我的程序正在搜索大量长度超过20,000的字符串，试图找到特定的唯一短语。

在C#中，什么是最有效的方法？

以下是当前的代码，它的工作方式如下：

1. 搜索从startPos开始，因为目标区域与开头有些偏差
2. 它循环遍历字符串，在每一步检查从该点开始的子串是否以startMatchString开头，这表明已找到目标字符串的开头。（目标字符串的长度不同）
3. 从这里开始，创建一个新的子字符串（截去标志目标字符串开始的11个字符），并搜索endMatchString。

我已经知道这是一个非常复杂且可能非常低效的算法。有没有更好的方法来实现相同的结果？

string result = string.Empty;    
for (int i = startPos; i <= response.Length - 1; i++)
{
   if (response.Substring(i).StartsWith(startMatchString))
   {
       string result = response.Substring(i).Substring(11);
       for (int j = 0; j <= result.Length - 1; j++)
       {
           if (result.Substring(j).StartsWith(endMatchString))
           {
               return result.Remove(j)
           }
       }
   }
}
return result;

- Harry

---

搜索的第二部分（查找endMatchString）并不是特别重要，因为与startMatchString的距离并不是很远（10-90个字符）。 - Andrew Harry

Answer 1

你可以使用String.IndexOf，但要确保使用StringComparison.Ordinal，否则它可能会慢一个数量级。

private string Search2(int startPos, string startMatchString, string endMatchString, string response) {
    int startMarch = response.IndexOf(startMatchString, startPos, StringComparison.Ordinal);
    if (startMarch != -1) {
        startMarch += startMatchString.Length;
        int endMatch = response.IndexOf(endMatchString, startMarch, StringComparison.Ordinal);
        if (endMatch != -1) { return response.Substring(startMarch, endMatch - startMarch); }
    }
    return string.Empty;
}

在183 KB文件的约40％位置搜索1000次字符串大约需要270毫秒。如果没有使用StringComparison.Ordinal，则需要大约2000毫秒。
使用您的方法进行1次搜索需要超过60秒，因为它在每次迭代时创建一个新字符串（O（n）），使得您的方法为O（n ^ 2）。

- ggf31416

Answer 2

有许多算法，

• Boyer-Moore算法
• Sunday算法
• Knuth-Morris-Pratt算法
• Rabin-Karp算法

我建议使用简化版的Boyer-Moore算法，即Boyer-Moore-Horspool算法。

C代码可在维基百科上找到。如果要查看Java代码，请访问：

http://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/BoyerMoore_java.html

关于这些算法的好文章可以在以下链接中找到：

http://www.ibm.com/developerworks/java/library/j-text-searching.html

如果想使用内置工具，请使用正则表达式。

- Luixv

Answer 3

这取决于您在字符串中想要查找什么。如果您正在寻找特定的序列，IndexOf/Contains 是快速的，但如果您正在寻找通配符模式，则 Regex 优化了这种搜索。

- Brian Rasmussen

---

起始和结束匹配字符串不会改变。重点是两者之间的字符串。 - Andrew Harry

@Harry：它在运行时是否固定，但在编译时未知，或者您想匹配通配符？对于后者，正则表达式是我的选择。尝试一下并进行分析以查看它是否足够快。 - Brian Rasmussen

@Brian: 开始和结束的匹配字符串在编译时是固定且已知的。 - Andrew Harry

Answer 4

我建议使用正则表达式来代替自己编写字符串搜索算法。你可以预编译正则表达式以提高运行速度。

- driis

Answer 5

你可以使用正则表达式；它是针对这种搜索和操作进行了优化的。

你也可以尝试使用IndexOf ...

string result = string.Empty;

if (startPos >= response.Length) 
    return result;

int startingIndex = response.IndexOf(startMatchString, startPos);
int rightOfStartIndex = startingIndex + startMatchString.Length;

if (startingIndex > -1 && rightOfStartIndex < response.Length)
{
    int endingIndex = response.IndexOf(endMatchString, rightOfStartIndex);
    if (endingIndex > -1)
        result = response.Substring(rightOfStartIndex, endingIndex - rightOfStartIndex);
}

return result;

- Nescio

---

真的吗？因为我经常听说正则表达式被认为是低效的。 - Andrew Harry

先试一下，如果需要再进行优化。 - Ed S.

Answer 6

这是一个使用IndexOf的例子（注意：这是我脑海中想到的，没有测试）：

int skip = 11;
int start = response.IndexOf(startMatchString, startPos);
if (start >= 0)
{
   int end = response.IndexOf(startMatchString, start + skip);
   if (end >= 0)
       return response.Substring(start + skip, end - start - skip);
   else
       return response.Substring(start + skip);
}
return string.Empty;

- oefe

Answer 7

对于非常长的字符串，您无法胜过Boyer-Moore搜索算法。 它比我在此尝试解释的要复杂，但The CodeProject网站上有一篇相当不错的文章介绍它。

- Khadaji

Answer 8

正如之前所说，正则表达式是你的好朋友。 你可能想要看一下RegularExpressions.Group。 这样你就可以为匹配结果集的某些部分命名。

这里有一个例子

- Ruben