概要

本問題は、円環状に配置された長さ \(N\) の文字列 \(S\) の中から、長さ \(M\) のパターン文字列 \(T\) と一致する開始位置の個数を求める問題です。

考察

素朴なアプローチとその限界

各開始位置 \(i \ (0 \leq i < N)\) について、円環上で \(i\) から始まる長さ \(M\) の文字列を愚直に切り出して \(T\) と比較する方法が考えられます。 しかし、この方法では1回の比較に最大 \(O(M)\) 時間かかり、全体で \(O(NM)\) 時間の計算量となります。 本問題の制約は \(N, M \leq 5 \times 10^5\) であるため、最悪の場合に計算回数が \(NM \approx 2.5 \times 10^{11}\) となり、実行時間制限（TLE）になってしまいます。 したがって、より高速な文字列検索アルゴリズムを適用する必要があります。

円環の直線化

円環状の文字列を扱うための典型的なアプローチとして、「文字列を繰り返して直線状にする」という方法があります。

開始位置の候補は \(0\) から \(N-1\) までの \(N\) 個です。 最も後ろの開始位置である \(N-1\) から始まる長さ \(M\) の文字列をカバーするためには、参照する最後の文字のインデックスは \((N-1) + (M-1) = N + M - 2\) となります。 したがって、0-indexed でインデックス \(N+M-2\) までをカバーするために、元の文字列 \(S\) を複数回繰り返して、長さ \(N + M - 1\) の文字列（これを \(text\) と呼びます）を作れば十分です。

\(M > N\) の場合（パターン文字列が円環を1周以上する場合）もあるため、\(S\) を繰り返す回数は \(\lceil M / N \rceil + 1\) 回必要になります。コード内では M // N + 2 回繰り返した文字列から必要な長さ \(N + M - 1\) を切り出しています。

高速なパターンマッチング

直線化された文字列 \(text\)（長さ \(N + M - 1\)）の中から、パターン \(T\)（長さ \(M\)）と完全に一致する箇所を探索します。 これには、線形時間 \(O(|text| + |T|)\) で動作する文字列検索アルゴリズムである KMP法 (Knuth-Morris-Pratt Algorithm) を使用します。

---

アルゴリズム

KMP法は、パターンの「自己対称性（接頭辞と接尾辞の一致）」を利用して、マッチングに失敗した際にポインタを戻す無駄を省くアルゴリズムです。

1. LPS配列の構築

パターン文字列 \(T\) について、各位置における「接頭辞であり、かつ接尾辞でもある最長のパターンの長さ（LPS: Longest Proper Prefix which is also Suffix）」を事前に計算します。 これにより、探索中に文字が不一致（ミスマッチ）となった際、パターンのどこまで戻って比較を再開すればよいかが分かります。この構築は \(O(M)\) 時間で行えます。

2. パターンの探索

テキスト \(text\) のポインタ \(i\) とパターン \(T\) のポインタ \(j\) を進めながら比較を行います。 - \(text[i] == T[j]\) の場合、両方のポインタを \(1\) 進めます。 - \(j == M\) に達した場合、パターンが完全一致したことを意味するため、答えのカウントを \(1\) 増やし、LPS配列を利用してポインタ \(j\) を戻します。 - \(text[i] \neq T[j]\) の場合： - \(j > 0\) であれば、ポインタ \(j\) を \(LPS[j-1]\) に戻して比較を再試行します。 - \(j == 0\) の場合は、これ以上戻れないため、テキストのポインタ \(i\) を \(1\) 進めます。

---

計算量

• 時間計算量: \(O(N + M)\)
  • \(S\) を繰り返した文字列から長さ \(N + M - 1\) の \(text\) を構築するのに \(O(N + M)\) 時間。
  • \(T\) のLPS配列の構築に \(O(M)\) 時間。
  • \(text\) から \(T\) を検索するKMP法の実行に \(O(N + M)\) 時間。
  • 全体として線形時間 \(O(N + M)\) で動作し、実行時間制限に余裕で間に合います。
• 空間計算量: \(O(N + M)\)
  • 長さ \(N + M - 1\) の文字列 \(text\) および、長さ \(M\) のLPS配列を保持するため、空間計算量は \(O(N + M)\) となります。

---

実装のポイント

• 文字列の切り出し: \(S\) を単純に何周もループさせながら探索するのではなく、あらかじめ必要な長さ \(N + M - 1\) の直線文字列 \(text\) を切り出しておくことで、境界条件（円環のつなぎ目）の処理をシンプルにし、バグの混入を防いでいます。

• \(M > N\) への対応: repeat_count = M // N + 2 とすることで、パターン \(T\) が円環を複数周するような極端なケースでも、正しく直線化された文字列を生成できます。

  ソースコード

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    S = data[0]
    T = data[1]

    N = len(S)
    M = len(T)

    repeat_count = M // N + 2
    S_double = S * repeat_count
    text = S_double[: N + M - 1]

    lps = [0] * M
    length = 0
    i = 1
    while i < M:
        if T[i] == T[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1

    ans = 0
    i = 0
    j = 0
    text_len = len(text)
    while i < text_len:
        if T[j] == text[i]:
            i += 1
            j += 1
            if j == M:
                ans += 1
                j = lps[j - 1]
        else:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

    print(ans)


if __name__ == "__main__":
    solve()

---

この解説は gemini-3.5-flash-thinking によって生成されました。