找到重复模式的最佳算法

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 个阶段组成。

• 选择图案
• 在输入字符串中查找模式（模式匹配算法）

它使用正则表达式进行模式匹配。还有其他更高级的算法。这些算法列于地址http://www-igm.univ-mlv.fr/~lecroq/string/ 但是，代码示例是用 C 编写的。此外，您还可以查看用于模式匹配的Boyer-Moore 算法，用 C# 编写