繰り返しで全体の文字列を作成するサブ文字列を見つける

Question

文字列「hrhrhrhrhr」があります。

私は、そのサブストリング自体を何度か追加して全体のストリングを作ることができるように、tの最小サブストリングを見つけたいと思います。

この例では、文字列 "hrhrhrhrhr"を "hr"を4回追加することでそれ自体を作成できます。

この種の部分文字列の検索方法は？ foxの例、 "abcabcabc"次に "abc"は答えです。

"ttttttt" - "t"は答えです。

"abcd" - > "abcd"は答えです。

アルゴリズムまたは特定の方法を使用する必要がありますか？

Answer 1

文字列の一致/検索アルゴリズムを見てみることをお勧めします。特に、KMP（Knuth-Morris Pratt）アルゴリズムを使用して文字列を検索すると、ルックアップテーブルによってパターンが生成されます。さらに、テーブル内の最も高い数字は、検索している部分文字列の最後の文字を返します（文字列が実際には部分文字列の繰り返しで構成されている場合）。