El mejor algoritmo para encontrar un patrón repetitivo

Question

¿Cuáles son los mejores algoritmos disponibles para encontrar los patrones más largos de repetición de caracteres en una cadena usando .net?

Answer 1

Supongo que hablas sobre descubrimiento de patrones. Echar un vistazo a algunos aproach primaria (source)

private static Dictionary<string, int> FindPatterns(string value) { 
    List<string> patternToSearchList = new List<string>(); 
    for (int i = 0; i < value.Length; i++) { 
    for (int j = 2; j <= value.Length/2; j++) { 
     if (i + j <= value.Length) { 
     patternToSearchList.Add(value.Substring(i, j)); 
     } 
    } 
    } 
    // pattern matching 
    Dictionary<string, int> results = new Dictionary<string, int>(); 
    foreach (string pattern in patternToSearchList) { 
    int occurence = Regex.Matches(value, pattern, RegexOptions.IgnoreCase).Count; 
    if (occurence > 1) { 
     results[pattern] = occurence; 
    } 
    } 

    return results; 
} 

static void Main(string[] args) { 
    Dictionary<string, int> result = FindPatterns("asdxgkeopgkajdflkjbpoijadadafhjkafikeoadkjhadfkjhocihakeo"); 
    foreach (KeyValuePair<string, int> res in result.OrderByDescending(r => r.Value)) { 
    Console.WriteLine("Pattern:" + res.Key + " occurence:" + res.Value.ToString()); 
    } 
    Console.Read(); 
} 

El algoritmo constan de 2 etapas.

• Elija patrón
• patrón de descubrimiento en cadena de entrada (algoritmo de coincidencia de patrones )

Se utiliza expresiones regulares para la coincidencia de patrones. Hay otros algoritmos más avanzados. Estos algoritmos se dan de alta en la dirección de http://www-igm.univ-mlv.fr/~lecroq/string/ Sin embargo, ejemplos de código están escritos en C. También se tomaría un vistazo en Boyer-Moore algorithm de coincidencia de patrones, escrito en C#

Answer 2

Pseudocódigo:

For N=1 to InputString.Length-1 
    rotatedString = RotateStringByN(InputString,N) 
    For N=0 to InputString.Length-1 
    StringResult[N] = if (rotatedString[N]==InputString[N]) then 
          InputString[N] 
         else 
          Convert.ToChar(0x0).ToString() 
    RepeatedStrings[] = String.Split(StringResult, Convert.ToChar(0x0).ToString()) 
    SaveLongestStringFrom(RepeatedStrings) 

O ... solo mira aquí en SO thread para otras soluciones.