如何在大字符串中查找重复的短语

我想找出一种有效的方式来查找大字符串中的重复短语。该字符串将包含数百或数千个由空格分隔的单词。我已经包含了我目前使用的代码，但是在查找重复的短语时效率很低。如何在大字符串中查找重复的短语

public static string FindDuplicateSubstringFast(string s, string keyword, bool allowOverlap = true) 
{ 
    int matchPos = 0, maxLength = 0; 
    if (s.ToLower().Contains(keyword.ToLower())) 
     for (int shift = 1; shift < s.Length; shift++) 
     { 
      int matchCount = 0; 
      for (int i = 0; i < s.Length - shift; i++) 
      { 

       if (s[i] == s[i + shift]) 
       { 
        matchCount++; 
        if (matchCount > maxLength) 
        { 
         maxLength = matchCount; 
         matchPos = i - matchCount + 1; 
        } 
        if (!allowOverlap && (matchCount == shift)) 
        { 
         // we have found the largest allowable match 
         // for this shift. 
         break; 
        } 
       } 
       else matchCount = 0; 
      } 
     } 
    string newbs = s.Substring(matchPos, maxLength); 
    if (maxLength > 3) return s.Substring(matchPos, maxLength); 
    else return null; 
}

我发现上面@Find duplicate content in string?

这种方法正在经历每一个字符，我想通过每个字的找一种方式来循环示例代码。我不确定什么是最好的方式来做到这一点。我想我可以在空白处分割字符串，然后将这些字词放入列表中。遍历列表应该比迭代每个字符更有效，就像我现在正在做的那样。但是，我不知道如何遍历列表并找到重复的短语。

如果有人能帮我找出一个算法遍历列表来找到重复的短语，我将非常感激。我也会接受任何其他的想法或方法来在大字符串中查找重复的短语。

如果需要更多信息，请让我知道。

编辑： 这是一个大的字符串{其小型这个例子}的例子

Lorem存有是印刷的只是虚拟的文本排版行业。自从16世纪以来，Lorem Ipsum一直是业界标准的虚拟文本。

例如清酒“Lorem Ipsum”将是重复的短语。我需要返回“Lorem Ipsum”以及任何其他重复出现在字符串中的重复短语。

来源

2013-09-28 Keefe Higgins

您可能会发现https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton有用。其他的数据结构也有链接，这些链接也可以帮助你。 –

否则，您可以将字符串拆分为split（），然后将每个单词添加到散列表（我更习惯于Java，因此我不记得C＃的版本是什么）。然后遍历你的hashmap并取出任何大于1的键。 –

'Dictionary'是Java的'HashMap'的.Net等价物。 –

string[] split = BigString.Split(' ').ToLower(); 
var duplicates = new Dictionary<string, int>(); 
for (int i = 0;i<split.Length;i++) 
{ 
    int j=i; 
    string s = split[i] + " "; 
    while(i+j<split.Length) 
    { 
     j++; 
     s += split[j] + " "; 
     if (Regex.Matches(BigString.ToLower(), s).Count ==1) break; 
     duplicates[s] = Regex.Matches(BigString.ToLower(), s).Count; 
    } 
}

现在，词典将包含所有的短语和“子短语”，例如“Lorem Ipsum Dolor”会找到“Lorem Ipsum”和“Lorem Ipsum Dolor”。如果这对你不感兴趣，这只是通过Keys收集duplicates的循环。如果一个密钥是另一个密钥的子串，并且它们的值相同，则删除所述密钥。

来源

2013-09-28 22:57:21 jose

我更新我的帖子以显示一个带有重复短语的字符串的小例子。短语在字符串中不分隔。 –

我已更新我的答案，希望它有帮助。 – jose

我不得不做一些小小的调整，但这个伎俩。谢谢！ –

如何在大字符串中查找重复的短语

回答

相关问题