algorithm - 找出重复 2 次或更多次的最长子串

Question

我只是想编写逻辑来检查给定字符串的最长子字符串，该字符串重复 2 次或 2 次以上

ex - 字符串 str = aabbcaaaaaaaabbcaaabbccaabddaab

      To find out Longest substring which repeated 2 or more times.

      output:  aabbcaa

Answer 1

为了有效地做到这一点，您应该考虑尝试。

这是有关使用尝试的教程的链接。特别是前缀树。

Answer 2

这是一个简单（但效率低下）的算法：循环所有可能的子字符串长度，从最大值到 1。对于每个长度，将该长度的所有子字符串放入字典中。如果发现重复，请停止。它应该是最大的一个。下面是对应的 C# 代码：

public static string FindDuplicateSubstring(string s)
    {
        for (int len = s.Length-1; len > 0; len--) {
            var dict = new Dictionary<string, int>();
            for (int i = 0; i <= s.Length - len; i++) {
                string sub = s.Substring(i, len);
                if (dict.ContainsKey(sub)) return sub;
                else dict[sub] = i;
            }
        }
        return null;
    }

例如，当应用于您的问题文本时，最长的重复子字符串是“实现”。请注意，允许重叠子字符串，即输入“bbbb”返回“bbb”。如果您想排除重叠案例，您的问题并不清楚。有关更快的方法，请参阅我的其他答案。

或者

好的例子。这里

我必须先对 ArrayList 进行排序，然后将 ontacts[ i ] 与 contacts[ i-1 ] 进行比较

contacts.Sort();


for (int i=1; i <= contacts.Count-1; i++)
{
Console.WriteLine(contacts[ i ]);
Console.WriteLine(contacts[ i-1] );
if(contacts[ i ].ToString() == contacts[ i-1 ].ToString())
{
Console.WriteLine("Duplicate: "+contacts[ i ]);
}
}