JavaScriptで2つの文字列の最大公約数（GCD）を求める方法

数学における最大公約数（GCD：Greatest Common Divisor）とは、2つの整数をどちらも割り切る最大の数のことです。この概念を文字列に応用すると、2つの文字列のGCDは、両方の文字列を構成できる最長の部分文字列（共通パターン）を意味します。

具体例

例えば、次の2つの文字列があるとします。

const str1 = 'abcabc';
const str2 = 'abc';

この場合、「abcabc」は「abc」を2回繰り返した文字列なので、2つの文字列のGCDは以下のようになります。

const gcd = 'abc';

ここでは、2つの文字列 str1 と str2 を引数として受け取り、それらのGCDを計算して返すJavaScript関数を実装します。

実装コード

const str1 = 'abcabc';
const str2 = 'abc';
const findGCD = (str1 = '', str2 = '') => {
    if (str1 + str2 !== str2 + str1){
        // 共通のパターンが存在しない場合
        return "";
    } else if (str1 == str2){
        return str1;
    } else if (str1.length > str2.length){
        return findGCD(str1.slice(str2.length), str2);
    } else {
        return findGCD(str2.slice(str1.length), str1);
    }
};
console.log(findGCD(str1, str2));

実行結果

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

abc

仕組みの解説

このアルゴリズムは、整数の最大公約数を求める際に使われるユークリッドの互除法と同じ発想を文字列に適用したものです。処理の流れは以下の通りです。

• 結合チェック： str1 + str2 !== str2 + str1 の場合、2つの文字列に共通する繰り返しパターンは存在しないため、空文字列を返します。これは共通パターンの有無を判定する重要な条件です。
• 等しい場合： 2つの文字列が完全に一致していれば、その文字列自体がGCDとなります。
• 再帰的な削減： 長さが異なる場合は、長い方の文字列の先頭から短い方と同じ長さの部分を切り取り、残りの文字列で関数を再帰的に呼び出します。これを繰り返すことで、最終的に共通のパターンが導き出されます。

この手法を使えば、コードはシンプルなまま、どのような文字列の組み合わせでも正しくGCDを求めることができます。