[解決済み] 文字列がすべて同じ部分文字列で構成されているかどうかを調べるにはどうすればよいですか？

質問

文字列を受け取る関数を作成する必要があります。 true または false は、入力が繰り返される文字列から構成されているかどうかに 基づいています。与えられた文字列の長さは，常に 1 よりも大きく、文字列は少なくとも1つの繰り返しを持たなければなりません。

"aa" // true(entirely contains two strings "a")
"aaa" //true(entirely contains three string "a")
"abcabcabc" //true(entirely containas three strings "abc")

"aba" //false(At least there should be two same substrings and nothing more)
"ababa" //false("ab" exists twice but "a" is extra so false)

以下のような関数を作りました。

function check(str){
  if(!(str.length && str.length - 1)) return false;
  let temp = '';
  for(let i = 0;i<=str.length/2;i++){
    temp += str[i]
    //console.log(str.replace(new RegExp(temp,"g"),''))
    if(!str.replace(new RegExp(temp,"g"),'')) return true;
  }
  return false;
}

console.log(check('aa')) //true
console.log(check('aaa')) //true
console.log(check('abcabcabc')) //true
console.log(check('aba')) //false
console.log(check('ababa')) //false

これをチェックすることが、本当の問題の一部なのです。こんな非効率的な解決策は許されない。まず、文字列の半分をループしている。

第二の問題は、それが replace() を使用しているため、動作が遅くなります。パフォーマンスに関してより良い解決策はあるのでしょうか？

どのように解決するのですか？

このような文字列には気の利いた定理があるのです。

文字列がそれ自身の非自明な回転である場合に限り、文字列は同じパターンを複数回繰り返すことで構成される。

ここで回転とは、文字列の前方からある数の文字を削除し、後方に移動させることを意味する。例えば、文字列 hello という文字列は、回転してこれらの文字列のいずれかになります。

hello (the trivial rotation)
elloh 
llohe 
lohel 
ohell 

なぜこれがうまくいくかというと、まず、文字列がある文字列wのk個の繰り返しコピーからできていると仮定すると、文字列の前から繰り返しパターン（w）の最初のコピーを削除し、後ろに張り付けると同じ文字列が戻ってきます。逆方向は証明するのが少し難しいですが、文字列を回転させて最初のものを取り戻すと、その回転を繰り返し適用して、同じパターンの複数のコピーで文字列をタイル状にすることができるということです (そのパターンは、回転を行うために端に移動する必要があった文字列です)。

さて、問題はこれが事実であるかどうかをどのように確認するかです。そのために、もう一つ使える美しい定理があります。

xとyが同じ長さの文字列であるとき、xがyyの部分文字列であるときのみ、xはyの回転である。

例として、以下のようになります。 lohel の回転であることがわかります。 hello を以下のように回転させる。

hellohello
   ^^^^^

この場合、すべての文字列xは常にxxの部分文字列であることが分かっている（xの各コピーで1回ずつ、2回現れる）。ですから、基本的には、文字列xがxxの部分文字列であるかどうかを、最初の文字や途中の文字でマッチしないようにチェックすればよいのです。以下はそのためのワンライナーです。

function check(str) {
    return (str + str).indexOf(str, 1) !== str.length;
}

仮定の話 indexOf が高速な文字列マッチングアルゴリズムを用いて実装されている場合、これは時間O(n)で実行されます（nは入力文字列の長さ）。

これが役に立つことを願っています。