Overview

This problem asks us to find the number of starting positions where pattern \(T\) matches in a string \(S\) arranged in a circular manner. We solve it using efficient pattern matching with the KMP algorithm.

Analysis

Problems with the Naive Approach

If we compare \(M\) characters one by one for each starting position \(i\), it takes \(O(NM)\) time. Since \(N, M\) can be up to \(5 \times 10^5\), this requires up to \(2.5 \times 10^{11}\) operations in the worst case, resulting in TLE.

Key Observations

Case 1: When \(M \leq N\)

The operation of reading \(M\) characters starting from position \(i\) on the circular string (which stays within one cycle since \(M \leq N\)) is equivalent to standard substring matching on the string \(S + S\) (i.e., \(S\) repeated twice). Specifically, we search for \(T\) within the first \(N + M - 1\) characters of \(S + S\), and count only matches whose starting positions are from \(0\) to \(N-1\).

Case 2: When \(M > N\)

The pattern wraps around the circle multiple times. The \(j\)-th character of the string \(R_i\) read from position \(i\) is \(S[(i+j) \bmod N]\). For this to match \(T[j]\), particularly when both \(j\) and \(j+N\) are less than \(M\), we need \(T[j] = S[(i+j) \bmod N] = T[j+N]\).

In other words, a necessary condition is that \(T\) has period \(N\) (i.e., \(T[j] = T[j+N]\) holds for all \(0 \leq j < M-N\)). If this condition is not satisfied, the answer is \(0\).

When this periodicity holds, by induction \(T[j] = T[j \bmod N]\) holds for all \(j\). Therefore, we only need to match the first \(N\) characters of \(T\) against the circular string \(S\), reducing this to Case 1.

Algorithm

1. Preprocessing when \(M > N\): Verify that \(T[j] = T[j+N]\) (\(0 \leq j < M-N\)). If not satisfied, the answer is \(0\). If satisfied, truncate \(T\) to \(T[0:N]\) and set \(M = N\).

2. Text construction: Create text = S + S[:M-1]. This string contains all possible results of reading up to \(M\) characters from any position on the circular string.

3. Search using KMP:

   • Build the failure function for \(T\).
   • Search for \(T\) in text and count matches whose starting positions are at least \(0\) and less than \(N\).

Overview of KMP Algorithm

KMP is an algorithm that precomputes the “longest proper prefix which is also a suffix” (failure function) for the pattern. This allows skipping unnecessary comparisons on mismatch and searching through the text without backtracking.

Complexity

• Time complexity: \(O(N + M)\) (both the preprocessing and searching phases of KMP are linear)
• Space complexity: \(O(N + M)\) (for text construction and storing the failure function)

Implementation Notes

• Text construction: By using S + S[:M-1], when \(M = 1\), S[:0] becomes an empty string, so the text becomes just \(S\) itself. In the code, the suffix is appended only when M > 1.

• Filtering match positions: Even when a match is found in text, matches with starting positions \(\geq N\) must be excluded because they would result in double-counting the same position on the circular string.

• Periodicity check when \(M > N\): Although it may seem complex, we simply check \(T[j] = T[j+N]\) sequentially for \(j = 0, 1, \ldots, M-N-1\). If even one position has a mismatch, we can immediately output \(0\).

  Source Code

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()

---

This editorial was generated by claude4.6opus-thinking.