文字列を受け取り、入力が繰り返しの文字シーケンスで構成されているかどうかに基づいてtrueまたはを返す関数を作成する必要があります。指定された文字列の長さは常に より大きく、文字シーケンスには少なくとも 1 つの繰り返しが含まれている必要があります。false1
"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これを確認することが実際の問題の一部です。このような非効率的な解決策は許容できません。まず第一に、文字列の半分をループしています。
2 番目の問題は、replace()各ループで を使用しているため、速度が遅くなることです。パフォーマンスに関して、より良い解決策はありますか?
ベストアンサー1
このような文字列については、ちょっとした気の利いた定理があります。
文字列は、文字列自体の非自明な回転である場合にのみ、複数回繰り返される同じパターンで構成されます。
ここで、回転とは、文字列の先頭からいくつかの文字を削除し、それらを後ろに移動することを意味します。たとえば、文字列を回転して、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 は入力文字列の長さです。