如何在大字符串中查找重複的短語

我想找出一種有效的方式來查找大字符串中的重複短語。該字符串將包含數百或數千個由空格分隔的單詞。我已經包含了我目前使用的代碼，但是在查找重複的短語時效率很低。如何在大字符串中查找重複的短語

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

我不得不做一些小小的調整，但這個伎倆。謝謝！ –

如何在大字符串中查找重複的短語

回答

相關問題