【JavaScript】文字列が同一部分文字列の繰り返しで構成されているか判定する方法

問題概要

文字列を1つだけ引数として受け取り、その文字列が「ある部分文字列を複数回連結したもの」になっているかどうかを判定するJavaScript関数を実装します。

たとえば、関数への入力が次の場合：

const str = 'thisthisthisthis';

期待される出力は以下のとおりです。

const output = true;

出力の説明

この文字列は「this」という部分文字列を4回繰り返して構成されているため、true が返されます。

実装コード

この問題を解くコードは次のようになります。

const str = 'thisthisthisthis';
const repeatedSubstring = (str = '') => {
    const {length} = str;
    const checkSubString = ss => {
        const m = ss.length;
        for (let i = 0; i < length; i += m)
            for (let j = 0; j < m; j++)
                if (str[i+j] !== ss[j])
                    return false;
        return true;
    };
    let factor = 2, len;
    while (length/factor >= 1){
        while (length % factor) factor++;
        len = length/factor;
        if (checkSubString(str.substring(0,len))){
            return true;
        };
        factor++;
    };
    return false;
};
console.log(repeatedSubstring(str));

コードの解説

まず、指定した部分文字列パターンを繰り返すことで文字列全体を正確に再現できるかどうかを検証するヘルパー関数 checkSubString を定義します。

続いて、元の文字列の長さを割り切れるすべての約数（factor）についてループ処理を行い、それぞれの約数に対応する長さの接頭辞（先頭からの部分文字列）を取り出します。この接頭辞を繰り返した結果が元の文字列と完全に一致すれば、有効な繰り返しパターンが存在することになるため true を返します。すべての候補を試しても一致しなければ false を返します。

計算量

• 時間計算量：O(n × d) ―― n は文字列の長さ、d は n の約数の個数です。各候補パターンに対して文字列全体を線形に走査します。
• 空間計算量：O(1) ―― substring() による一時的な文字列生成を除けば、追加のメモリはほとんど不要です。

別解：より簡潔なトリック

文字列を2回連結したものから先頭と末尾の1文字ずつを取り除いた中間部分に、元の文字列が含まれているかどうかを調べる方法もあります。この性質を利用すると、繰り返し構造の有無をわずか数行で判定できます。

const repeatedSubstring = (str = '') => {
    if (str.length < 2) return false;
    return (str + str).slice(1, -1).includes(str);
};
console.log(repeatedSubstring('thisthisthisthis')); // true

これは、文字列が何らかの単位パターンの繰り返しである場合、その文字列自身をシフトしたものが必ず元の文字列と重なり合うという性質に基づいた有名なテクニックです。

出力結果

コンソールには次のように表示されます。

true