効率的なアルゴリズムとC++の文字列でサイクルを見つけるためのコード？

たとえば、 "12345123451234512345"では、 "12345"を見つける効率的なアルゴリズムは何ですか？効率的なアルゴリズムとC++の文字列でサイクルを見つけるためのコード？

C++でのコーディング。

ありがとうございました。あなたの単一の例に行く

2010-12-04 B Seven

この宿題はありますか？もしそうなら、言いたいことは丁寧です。また、「send me tez codez」の質問は良い答えを得ることもほとんどありません。何を試しましたか？どんな問題に遭遇しましたか？ –

質問には、「サイクル」とは何か、文字列に見つかったものがあるかどうかについては十分に具体的ではありません。 – zwol

これは数字だけですか？あなたはサイクルがどれくらい大きいか手掛かりを持っていますか？それとも何回繰り返されますか？ – Falmarri

：

12345123451234512345戻り12345

私はあなたが何をしたいと思うには、干し草の山を完了させるために繰り返されるできるだけ長い針を見つけることです、つまり1212121212 =>12、444 =>4など。

最も簡単な解決策は、最初の文字を選択し、一致する文字列を比較することです。いずれかの時点で不一致がある場合は、ウィンドウサイズが文字列の半分より大きくなるまで、最初の2文字を選択して文字列全体を実行します。

複雑さはO（n^2）である必要があり

あなたはすなわち、ウィンドウサイズが唯一の文字列の長さの約数であることができ、あなたは文字列の長さに基づいて選択され、ウィンドウサイズを最適化することができます。

2010-12-04 05:37:08

可能な限り長くしている場合、例では "1234512345"という文字列が2回繰り返されていませんか？ – abelenky

@abelenky：ウィンドウはサイズ1より大きくなります。私のアルゴリズムでは、文字列全体と一致するので12345で停止します。） –

444は答えが44ではありませんか？ –

答えて