Лучший алгоритм поиска повторяющегося паттерна

Question

Какие лучшие алгоритмы доступны для поиска длинных повторяющихся комбинаций символов в строке с использованием .net?

Answer 1

Полагаю, вы говорите о обнаружении паттернов .Взгляните на некоторый элементарный подход ( источник )

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

Алгоритм состоит из 2 этапов.

• Выбор шаблона
• Поискшаблон во входной строке (алгоритм сопоставление с образцом )

Используется Regex для сопоставления с образцом.Есть и другие более продвинутые алгоритмы.Эти алгоритмы зачислены по адресу http://www -igm.univ-mlv.fr / ~ lecroq / string / Однако примеры кода написаны на C. Также вы можете взглянуть на BoyerАлгоритм Мура для сопоставления с образцом, написанный на C #

Answer 2

псевдокод:

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)

... Или просто посмотрите здесь ТА потока для других решений.