Método de búsqueda más rápido en StringBuilder

Gerardo, parte de nuestro staff, nos ha hecho el favor de crear este post porque conoce muy bien dicho tema.

Solución:

StringBuilder no estaba realmente destinado a todos string propósitos Si realmente necesita buscar uno, debe escribir su propio método.

Hay varios string-Algoritmos de búsqueda adecuados a diferentes casos.

La siguiente es una implementación simple del algoritmo de Knuth-Morris-Pratt que solo se preocupa por las coincidencias ordinales (sin duplicación de casos, sin intercalación relacionada con la cultura, solo una simple coincidencia de punto de código a punto de código). tiene alguna inicial Θ(m) arriba donde m es la longitud de la palabra buscada, y luego encuentra en Θ(n) donde n es la distancia a la palabra buscada, o la longitud de todo string-constructor si no está allí. Esto supera la simple comparación de carácter por carácter que es Θ((n-m+1) m) (Donde O() notación describe límites superiores, Θ() describe los límites superior e inferior).

Dicho todo esto, parece que crear una lista podría ser un mejor enfoque para la tarea en cuestión.

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)
   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;
  

Reseñas y puntuaciones del tutorial

Si piensas que ha sido de utilidad este artículo, sería de mucha ayuda si lo compartes con otros seniors así nos ayudas a difundir este contenido.

---

---

Utiliza Nuestro Buscador