Overview

This problem asks us to find the number of starting positions in a circular string \(S\) of length \(N\) where a pattern string \(T\) of length \(M\) matches.

Analysis

Naive Approach and Its Limitations

One possible approach is, for each starting position \(i \ (0 \leq i < N)\), to extract the substring of length \(M\) starting at position \(i\) on the circular string and compare it directly with \(T\). However, this method takes up to \(O(M)\) time per comparison, resulting in an overall time complexity of \(O(NM)\). Given the constraints of this problem where \(N, M \leq 5 \times 10^5\), the worst case would require \(NM \approx 2.5 \times 10^{11}\) operations, which would exceed the time limit (TLE). Therefore, we need to apply a faster string searching algorithm.

Linearizing the Circular String

A standard approach for handling circular strings is to “repeat the string to make it linear.”

The candidate starting positions range from \(0\) to \(N-1\), giving \(N\) positions in total. To cover the substring of length \(M\) starting at the last starting position \(N-1\), the index of the last character referenced is \((N-1) + (M-1) = N + M - 2\). Therefore, to cover up to index \(N+M-2\) in 0-indexed terms, it suffices to repeat the original string \(S\) multiple times and create a string of length \(N + M - 1\) (which we call \(text\)).

Since \(M > N\) is possible (the pattern string may wrap around the circle more than once), the number of repetitions of \(S\) needs to be \(\lceil M / N \rceil + 1\). In the code, we repeat the string M // N + 2 times and then extract the required length \(N + M - 1\).

Fast Pattern Matching

We search for positions in the linearized string \(text\) (of length \(N + M - 1\)) that exactly match the pattern \(T\) (of length \(M\)). For this, we use the KMP algorithm (Knuth-Morris-Pratt Algorithm), a string searching algorithm that runs in linear time \(O(|text| + |T|)\).

---

Algorithm

The KMP algorithm exploits the “self-symmetry (matching of prefixes and suffixes)” of the pattern to avoid unnecessary backtracking of the pointer when a mismatch occurs.

1. Building the LPS Array

For the pattern string \(T\), we precompute the “Longest Proper Prefix which is also a Suffix (LPS)” at each position. This tells us where to resume comparison in the pattern when a character mismatch occurs during the search. This construction takes \(O(M)\) time.

2. Pattern Search

We advance and compare a pointer \(i\) for the text \(text\) and a pointer \(j\) for the pattern \(T\). - If \(text[i] == T[j]\), advance both pointers by \(1\). - If \(j == M\) is reached, this means the pattern has been fully matched, so we increment the answer count by \(1\) and use the LPS array to move pointer \(j\) back. - If \(text[i] \neq T[j]\): - If \(j > 0\), move pointer \(j\) back to \(LPS[j-1]\) and retry the comparison. - If \(j == 0\), we cannot backtrack further, so advance the text pointer \(i\) by \(1\).

---

Complexity

• Time Complexity: \(O(N + M)\)
  • Constructing \(text\) of length \(N + M - 1\) from the repeated string \(S\) takes \(O(N + M)\) time.
  • Building the LPS array for \(T\) takes \(O(M)\) time.
  • Running the KMP algorithm to search for \(T\) in \(text\) takes \(O(N + M)\) time.
  • Overall, it runs in linear time \(O(N + M)\), comfortably within the time limit.
• Space Complexity: \(O(N + M)\)
  • Since we store the string \(text\) of length \(N + M - 1\) and the LPS array of length \(M\), the space complexity is \(O(N + M)\).

---

Implementation Notes

• String Extraction: Rather than searching while looping around \(S\) multiple times, we pre-extract the linear string \(text\) of the required length \(N + M - 1\). This simplifies the handling of boundary conditions (the circular wrap-around point) and prevents bugs.

• Handling \(M > N\): By setting repeat_count = M // N + 2, we can correctly generate the linearized string even in extreme cases where the pattern \(T\) wraps around the circle multiple times.

  Source Code

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

---

This editorial was generated by gemini-3.5-flash-thinking.