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

Question

我正在尝试找出一种在大字符串中查找重复短语的有效方法。该字符串将包含由空格分隔的数百或数千个单词。我在下面包含了我目前正在使用的代码，但查找重复短语的效率非常低。

    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? 找到了上面的示例代码

此方法遍历每个字符，我想找到一种遍历每个单词的方法。我不确定执行此操作的最佳方法是什么。我在想我可以在空白处拆分字符串，然后将单词放入列表中。遍历列表应该比像我现在做的那样遍历每个字符更有效。但是，我不知道如何遍历列表并找到重复的短语。

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

如果需要更多信息，请告诉我。

编辑:这里是一个大字符串的例子{its small for this example}

Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry's standard dummy text ever since the 1500s.

例如，sake "Lorem Ipsum"将是重复的短语。我需要返回“Lorem Ipsum”和在字符串中多次出现的任何其他重复短语。

Answer 1

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 即可。如果一个键是另一个键的子字符串，并且它们的值相同，则删除该键。