StringBuilder中最快的搜索方法

Question

我有一个StringBuilder命名stb_Swap_Tabu用来存储课程的名称,我使用下面的方法找到一个过程:

stb_Swap_Tabu.ToString.Contains("CourseName")

就我而言,性能是最重要的问题.有没有更快的方法？

Answer 1

StringBuilder并非真正用于所有字符串目的.如果你真的需要搜索一个,你必须编写自己的方法.

有几种适合不同情况的字符串搜索算法.

以下是Knuth-Morris-Pratt算法的简单实现,该算法仅关注序数匹配(没有大小写折叠,没有与文化相关的排序规则,只是简单的码点匹配代码点).它有一些初步?(m)的开销这里m是寻求字的长度,然后在发现?(n)哪里n是寻求的字,或整个字符串建设者的长度的距离,如果它不存在.这比简单的char-by-char比较更好?((n-m+1) m)(其中O()符号描述了上限,?()描述了上限和下限).

所有这些都说,听起来好像创建一个列表可能是一个更好的方法来完成手头的任务.

public static class StringBuilderSearching
{
  public static bool Contains(this StringBuilder haystack, string needle)
  {
    return haystack.IndexOf(needle) != -1;
  }
  public static int IndexOf(this StringBuilder haystack, string needle)
  {
    if(haystack == null || needle == null)
      throw new ArgumentNullException();
    if(needle.Length == 0)
      return 0;//empty strings are everywhere!
    if(needle.Length == 1)//can't beat just spinning through for it
    {
      char c = needle[0];
      for(int idx = 0; idx != haystack.Length; ++idx)
        if(haystack[idx] == c)
          return idx;
      return -1;
    }
    int m = 0;
    int i = 0;
    int[] T = KMPTable(needle);
    while(m + i < haystack.Length)
    {
      if(needle[i] == haystack[m + i])
      {
        if(i == needle.Length - 1)
          return m == needle.Length ? -1 : m;//match -1 = failure to find conventional in .NET
        ++i;
      }
      else
      {
        m = m + i - T[i];
        i = T[i] > -1 ? T[i] : 0;
      }
    }
    return -1;
  }      
  private static int[] KMPTable(string sought)
  {
    int[] table = new int[sought.Length];
    int pos = 2;
    int cnd = 0;
    table[0] = -1;
    table[1] = 0;
    while(pos < table.Length)
      if(sought[pos - 1] == sought[cnd])
        table[pos++] = ++cnd;
      else if(cnd > 0)
        cnd = table[cnd];
      else
        table[pos++] = 0;
    return table;
  }
}