概要

円環状に並んだ文字列 \(S\) に対して、パターン \(T\) が一致する開始位置の個数を求める問題です。KMP法を用いた効率的なパターンマッチングで解きます。

考察

素朴なアプローチの問題点

各開始位置 \(i\) について \(M\) 文字を1文字ずつ比較すると、\(O(NM)\) の時間がかかります。\(N, M\) が最大 \(5 \times 10^5\) のため、最悪 \(2.5 \times 10^{11}\) 回の操作が必要となり、TLEになります。

重要な気づき

ケース1: \(M \leq N\) の場合

円環上で位置 \(i\) から \(M\) 文字（\(M \leq N\) なので1周以内）を読む操作は、文字列 \(S\) を2回繰り返した \(S + S\) 上での通常の部分文字列マッチングと等価です。具体的には、\(S + S\) の先頭 \(N + M - 1\) 文字の中で \(T\) を検索し、開始位置が \(0\) から \(N-1\) のものだけを数えればよいです。

ケース2: \(M > N\) の場合

パターンが円環を複数周回します。位置 \(i\) から読む文字列 \(R_i\) の \(j\) 文字目は \(S[(i+j) \bmod N]\) です。これが \(T[j]\) と一致するためには、特に \(j\) と \(j+N\) が共に \(M\) 未満のとき \(T[j] = S[(i+j) \bmod N] = T[j+N]\) が必要です。

つまり、\(T\) が周期 \(N\) を持つ（\(T[j] = T[j+N]\) がすべての \(0 \leq j < M-N\) で成立する）ことが必要条件です。この条件が満たされない場合、答えは \(0\) です。

この周期性が成り立つ場合、帰納的に \(T[j] = T[j \bmod N]\) が全ての \(j\) で成り立ちます。したがって、\(T\) の最初の \(N\) 文字だけを円環 \(S\) と照合すればよく、ケース1に帰着できます。

アルゴリズム

1. \(M > N\) の場合の前処理: \(T[j] = T[j+N]\)（\(0 \leq j < M-N\)）を確認。不成立なら答えは \(0\)。成立なら \(T\) を \(T[0:N]\) に短縮し、\(M = N\) とする。

2. テキストの構築: text = S + S[:M-1] を作る。この文字列は、円環上の任意の位置から最大 \(M\) 文字を読んだ結果を全て含む。

3. KMP法で検索:

   • \(T\) の失敗関数（failure function）を構築する。
   • text 上で \(T\) を検索し、マッチの開始位置が \(0\) 以上 \(N\) 未満のものを数える。

KMP法の概要

KMP法は、パターンの「接頭辞と接尾辞が一致する最大長」を前計算（失敗関数）しておくことで、ミスマッチ時に無駄な比較をスキップし、テキスト上を後戻りせずに検索するアルゴリズムです。

計算量

• 時間計算量: \(O(N + M)\)（KMP法の前処理と検索がそれぞれ線形）
• 空間計算量: \(O(N + M)\)（テキストの構築と失敗関数の格納）

実装のポイント

• テキストの構築: S + S[:M-1] とすることで、\(M = 1\) の場合に S[:0] = 空文字列となり、テキストが \(S\) そのものになる点に注意。コード中では M > 1 のときのみ末尾を付加している。

• マッチ位置のフィルタリング: text 上でマッチが見つかっても、開始位置が \(N\) 以上のものは円環上の同じ位置を重複カウントしてしまうため除外する。

• \(M > N\) の周期性チェック: 一見複雑だが、\(T[j] = T[j+N]\) を \(j = 0, 1, \ldots, M-N-1\) について順にチェックするだけでよい。1箇所でも不一致があれば即座に \(0\) を出力できる。

  ソースコード

import sys
from math import gcd

def solve():
    input_data = sys.stdin.buffer.read().decode()
    lines = input_data.split()
    S = lines[0]
    T = lines[1]
    N = len(S)
    M = len(T)
    
    # Special case: if M < N, we just do pattern matching on S+S (length 2N), 
    # but only consider matches starting at positions 0..N-1
    # If M == N, same approach works
    # If M > N, the pattern wraps around multiple times
    
    # For M > N case:
    # R_i matches T iff for all j in 0..M-1: S[(i+j) % N] == T[j]
    # This means T[j] == T[j + N] for all valid j (periodicity condition on T with period N)
    # And the first N characters of the "virtual" match must match.
    
    if M > N:
        # Check that T has period N: T[j] == T[j+N] for all j where j+N < M
        # i.e., T must be consistent with period N
        for j in range(M - N):
            if T[j] != T[j + N]:
                print(0)
                return
        # Now we only need to match the first min(M, N) characters... 
        # Actually we need to match T[0..N-1] against the circular string, 
        # but also the "tail" T[k*N .. M-1] where k = M // N
        # Let's think again: after confirming periodicity, we need T[0:N] to match 
        # starting at position i, BUT T might not have a full last period.
        # We need: for j=0..M-1, S[(i+j)%N] == T[j]
        # With period N confirmed, T[j] == T[j % N] for all j < M... 
        # Wait, that's only true if the period divides cleanly.
        # Actually T[j] == T[j mod N] for all j < M follows from T[j] == T[j+N] 
        # by induction. If j >= N, then T[j] == T[j-N], and by induction T[j-N] == T[(j-N) mod N] = T[j mod N].
        # So yes, T[j] = T[j mod N] for all j.
        # So we just need to match T[0:N] against circular S starting at position i.
        T = T[:N]
        M = N
    
    # Now M <= N
    # Build the text as S + S[:M-1] (to handle wrap-around), then find all occurrences of T
    # But only count those starting at positions 0..N-1
    
    if M == 0:
        print(N)
        return
    
    text = S + S[:M - 1] if M > 1 else S
    
    # KMP
    # Build failure function for T
    fail = [0] * M
    k = 0
    for i in range(1, M):
        while k > 0 and T[k] != T[i]:
            k = fail[k - 1]
        if T[k] == T[i]:
            k += 1
        fail[i] = k
    
    # Search
    count = 0
    k = 0
    text_len = len(text)
    for i in range(text_len):
        while k > 0 and T[k] != text[i]:
            k = fail[k - 1]
        if T[k] == text[i]:
            k += 1
        if k == M:
            # Match at position i - M + 1
            start = i - M + 1
            if start < N:
                count += 1
            k = fail[k - 1]
    
    print(count)

solve()

---

この解説は claude4.6opus-thinking によって生成されました。