Самый быстрый метод поиска в StringBuilder

Ответ 1

StringBuilder не был предназначен для всех строк. Если вам действительно нужно искать один, вы должны написать свой собственный метод.

Существует несколько алгоритмов поиска строк, подходящих для разных случаев.

Ниже приведена простая реализация алгоритма Кнута-Морриса-Пратта, который заботится только о порядковых совпадениях (без разборки, без сопоставления с культурами, просто для простого совпадения кодов). Он имеет некоторые начальные служебные данные Θ(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;
  }
}

Ответ 2

Я знаю, что это старый вопрос, но он появился в моих результатах поиска, когда я пытался создать решение для своего собственного проекта, где мне показалось, что мне нужно искать стробоструй, но потом я понял, что могу просто найти значение, которое Я использовал для инициализации построителя строк. Поэтому моя ситуация может быть не такой, как у вас, но я бы поделился ею:

Private Function valueFormatter(ByVal value As String) As String
        ' This will correct any formatting to make the value valid for a CSV format
        '
        ' 1) Any value that as a , in it then it must be wrapped in a " i.e. Hello,World -> "Hello,World"
        ' 2) In order to escape a " in the value add a " i.e. Hello"World -> Hello""World
        ' 3) if the value has a " in it then it must also be wrapped in a " i.e. "Hello World" -> ""Hello World"" -> """Hello World"""
        ' 
        ' VB NOTATAION 
        ' " -> """"
        ' "" -> """"""

        If value.Contains(",") Or value.Contains("""") Then
            Dim sb As New StringBuilder(value)
            If value.Contains("""") Then sb.Replace("""", """""")
            sb.Insert(0, """").Append("""")
            Return sb.ToString
        Else
            Return value
        End If
    End Function