Pythonで文字列が回転で一致するか判定する方法

文字列の回転マッチング問題とは

2つの文字列 A と B が与えられたとき、文字列 A を回転させて、いずれかの時点で B と一致するかどうかを判定する問題を考えてみましょう。一致する回転位置が存在すれば True を返し、存在しなければ False を返します。

例えば、A = 'abcde'、B = 'cdeab' の場合、A を2文字分回転させると 'cdeab' になるため、答えは True となります。一方、B = 'acdeb' のような場合はどれだけ回転しても一致しないため、False が返されます。

解法のアプローチ

この問題は「連結テクニック」を使うと効率的に解けます。基本的な考え方は以下の通りです。

• A と B が両方とも空文字列の場合は True を返す
• A と B の長さが異なる場合は、回転しても絶対に一致しないため False を返す
• A を自分自身と連結して A = A + A とする（これにより、A のすべての回転パターンが部分文字列として含まれる）
• 2つのポインタ i と j を使って、連結後の文字列の中で B と一致する箇所を線形探索する

アルゴリズムの詳細な手順

1. i = 0、j = 0 として初期化する
2. i が連結後の A の長さ未満である間、以下を繰り返す
   • 残りの文字数が B の長さより短くなったら False を返す
   • A[i] == B[j] が成り立つ限り、i と j を1ずつ増やす
   • j が B の長さに達したら、完全一致したことになるので True を返す
   • j が 0 でない場合は i を1減らし、j を 0 にリセットする
   • i を1増やして次の開始位置へ進む

Pythonでの実装例

それでは、実際のコードを見てみましょう。

class Solution(object):
    def rotateString(self, A, B):
        # 両方空なら True
        if not A and not B:
            return True
        # 長さが違えば False
        if len(A) != len(B):
            return False
        # A を自己連結して全回転パターンを含める
        A = A * 2
        i = 0
        j = 0
        while i < len(A):
            # 残り文字数が足りなければ不一致
            if len(A) - i + 1 < len(B):
                return False
            while i < len(A) and j < len(B) and A[i] == B[j]:
                i += 1
                j += 1
            # B を最後まで照合できたら一致
            if j == len(B):
                return True
            if j:
                i -= 1
            j = 0
            i += 1

ob1 = Solution()
print(ob1.rotateString("abcde", "cdeab"))

入力

"abcde"
"cdeab"

出力

True

補足：もっとシンプルな書き方

実は Python では、in 演算子を使えば上記のロジックを1行で表現できます。

def rotateString(self, A, B):
    return len(A) == len(B) and B in A + A

この書き方は、「B が A+A の部分文字列であり、かつ両者の長さが等しい」という条件で回転一致を判定しています。長さチェックを省くと 'ab' と 'a' のようなケースで誤判定されるため注意が必要です。

まとめ

• 文字列の回転判定には自己連結（A + A）が有効
• 時間計算量は O(n)、空間計算量も O(n)
• Python では B in A + A という簡潔な記述でも実装可能