Cの文字列の中で最短のプレフィックスを見つける

Question

私はCを新しくしており、コードで助けてくれてありがとう。 配列を動的に割り当て、文字列内のどの接頭辞が文字列を構築し連結するのが最短かをチェックして、それを長さにする必要があります。ここ

を出力するためのいくつかの例である： "ABABAB" の

1. 、出力は次のようになります "AAAA" の長さ2
2. の "AB" は、出力すべきである：「A abcaabca "の長さ1
3. の ""、出力すべきである： "ABCA" 長さ4
4. のための "ABCDEFG"、出力は次のようになります。 " "acacaac" の長さ7
5. の" ABCDEFG出力は長さ7の「acacaac」にする必要があります

私の問題は、私はそれに想定された機能をどのように構築するのか分かりません。文字列に同じ文字しか含まれていない場合や、すべての文字が異なる場合は問題ありませんが、他のすべての場合の処理​​方法はわかりません。

私はこのコードに別の文字列を使用することはできませんが、他のポインタ の使用を許可しています。

ありがとう

Answer 1

私は有効なコードを書くのではなく、アイデアそのものです。

まず、あなたのこの「プレフィックス」は、大きな長さの約数である長さを持っています。したがって、接頭辞の長さiが文字列の長さnを分割しない場合は、スキップする必要があります。

長さiが有効かどうかを調べるには、jの可能なすべての値に対して、位置jとj + iの文字を比較する必要があります。

Answer 2

これはかなり単純で、2つのネストされたループ、外側は1からlength/2、内側はwhileの繰り返し変数の値によって各ステップで増加したポインタを使用することができます外側ループ。ループの内部では、strncmp（）を使用して適切な部分文字列を比較し、比較が失敗した場合はループを中断できます。すべての比較がOKであれば、 "最短接頭辞"が見つかったので、（for）ループを壊すことができます。 forループは、入力文字列長の約数ではない長さをスキップすることによっても最適化できます。

これは、コピーを作成する必要はありません。

はい、実際にコードを書いておきます。

Answer 3

あなたは別の文字列を使うことはできないと言いました。文字列中の異なる文字の数をカウントするために小さな一時的なブール値の配列を使うことは許されています。

1ブール値の配列を使用して、文字列内の異なる文字数を検索します。この数をxとする。

2最初のx文字が接頭辞を構成するかどうかを確認します。 （各ポインタの位置pをp + x、p + 2xなどに照らしてチェックする）。失敗した場合、最短のプレフィックスは文字列全体です。

間には、x がを文字列の長さで割り切れるかどうかを素早く確認することで、より速くすることができます。