3

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

    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 Ipsum 只是印刷和排版行业的虚拟文本。自 1500 年代以来，Lorem Ipsum 一直是业界标准的虚拟文本。

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

4

1 回答 1

6 
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-28T22:57:21.843 回答