java - 文字列内のサイクル/繰り返しを見つける方法は?

Question

文字列内のサイクル/シーケンスを検出し、最初に出現したものを返す必要があります。どうすればいいですか？

例 ：

2 0 5 3 1 5 3 1 5 3 1

発生する最初のシーケンスは です5 3 1。

ルールはありません。シーケンスは文字列の長さの半分にすることができます。たとえば、

5 3123 1231 231 31 231 41 452 3453 21 312312 5 3123 1231 231 31 231 41 452 3453 21 312312

シーケンスは5 3123 1231 231 31 231 41 452 3453 21 312312

Answer 1

Floydsサイクル検出アルゴリズムを学習しましたか? サイクルを見つけたい場合は、これが役立つ場合があります。実装も非常に簡単です。

Answer 2

コメントに基づく明確化: サイクルとは、すぐに繰り返される一連の数字を意味します。そう

1 1

サイクルだろう

1 3 1

1 の潜在的なサイクルが 3 によって中断されるため、そうではありません。

1 3 1 3

はサイクル (1 3) です。

したがって、基本的なアルゴリズムは次のようになります。

1. 文字列の反復。

2. 数字ごとに、文字列内で次に出現するものを見つけます。何も見つからない場合は、次の文字に進みます。

3. 次の出現が見つかった場合は、現在の数字から次の出現までのシーケンスを、次の出現から始まる同じ長さのシーケンスと比較します。それらが同じ場合は、サイクルが見つかりました。そうでない場合は、次の発生に進みます。