Ala Ala - 1 year ago 76 Question

Fastest search method in StringBuilder

I have a

used to store Course's Names,
I am using the following method to find a course:


in my case, Performance is the most important issue.
Is there any faster way?

Answer Source

StringBuilder wasn't really intended for all string purposes. If you really need to search one, you have to write your own method.

There are several string-searching algorithms suited to different cases.

The following is a simple implementation of the Knuth–Morris–Pratt algorithm that only cares about ordinal matches (no case-folding, no culture-related collation, just a plain codepoint to codepoint match). It has some initial Θ(m) overhead where m is the length of the word sought, and then finds in Θ(n) where n is the distance to the word sought, or the length of the whole string-builder if it isn't there. This beats the simple char-by-char compare which is Θ((n-m+1) m) (Where O() notation describes upper-bounds, Θ() describes both upper and lower bounds).

All this said, it does sound like creating a list might be a better approach to the task in hand.

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
        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];
        table[pos++] = 0;
    return table;
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download