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

文字列の最大公約数とは

2つの文字列AとBがあると仮定します。AがBを1回以上連結することで作成できる場合、「AはBで割り切れる」と表現できます。例えば、A = "abcabc"、B = "abc" の場合、AはBの繰り返しで構成されているため、AはBで割り切れることになります。

この記事では、文字列の最大公約数（GCD）について解説します。これは、両方の文字列を割り切ることができる最も長い文字列を求める問題です。例えば、2つの文字列が "ABABAB" と "ABAB" の場合、共通して割り切れる最大の文字列は "AB" となるため、GCDは "AB" になります。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• temp := AとBのうち短い方の文字列を代入する
• m := tempの長さを取得する
• x := 1 で初期化する
• res は結果を格納する配列とし、空文字列 "" を挿入しておく
• x からなる接頭辞が両方の文字列を割り切れる間、その部分文字列をresに追加し、x を1ずつ増やす
• 最後に、res 配列の最後の要素（最も長い共通の割り算の元）を返す

ポイントは、候補となる部分文字列の長さ x が短い方の文字列の長さ m の約数であることを確認し、その接頭辞を繰り返したものが str1 と str2 の両方と一致するかどうかを検証する点です。これにより、無駄な比較を避けながら正確に判定できます。

実装例

以下のPythonコードは、上記の手順を実装したものです。

class Solution(object):
   def gcdOfStrings(self, str1, str2):
      if len(str1)<=len(str2):
         temp = str1
      else:
         temp = str2
      m = len(temp)
      x = 1
      res=[""]
      while x<=m:
         if m%x==0 and temp[:x] * (len(str1)//x) == str1 and temp[:x] * (len(str2)//x) == str2:
            res.append(temp[:x])
         x+=1
      return res[-1]
ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB","ABAB"))

入力

"ABABAB"
"ABAB"

出力

AB