algorithm - 2回以上繰り返された最長の部分文字列を見つけるには

Question

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;
    }

たとえば、質問のテキストに適用すると、最も長く繰り返される部分文字列は「implementation」です。重複する部分文字列が許可されていることに注意してください。つまり、入力 "bbbb" は "bbb" を返します。重複するケースを除外したい場合は、質問から明確ではありませんでした。より速いアプローチについては、他の回答を参照してください。

また

良い例え。ここ

最初に ArrayList をソートする必要があり、次に ontacts[ i ] と contact[ 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 ]);
}
}