Overview

This problem asks us to find how many starting positions exist in a circular string \(S\) where a contiguous substring matches the pattern string \(T\).

To handle the circular string, we create a new string \(S'\) by appropriately extending \(S\), and then apply the Z-algorithm, a fast pattern matching algorithm, to solve the problem efficiently.

---

Analysis

1. How to handle a circular string?

In a circular string \(S\) (of length \(N\)), consider the string \(R_i\) of length \(M\) starting at each position \(i\) (\(0 \leq i < N\)). For example, when \(S = \text{"abc"}\) (\(N=3\)) and \(T = \text{"cab"}\) (\(M=3\)), the \(3\) characters starting from position \(i=2\) wrap around from the end to the beginning, forming \(\text{"cab"}\).

The standard technique for handling this “the beginning follows after the end” circular property is to repeat and extend the string. There are \(N\) possible starting positions from \(0\) to \(N-1\), and from each we read up to \(M\) characters, so the maximum index accessed is \((N-1) + (M-1) = N + M - 2\).

Therefore, by creating a string \(S'\) of length \(N + M - 1\), filled with characters at position \(i \bmod N\) of the original string \(S\), we can represent all length-\(M\) strings from every starting position on the circle as linear substrings.

For \(S = \text{"abc"}\) (\(N=3\)), \(T = \text{"cab"}\) (\(M=3\)): \(S'\) becomes a string of length \(3 + 3 - 1 = 5\), giving \(S' = \text{"abcab"}\). - \(3\) characters from \(i = 0\): \(S'[0..2] = \text{"abc"}\) - \(3\) characters from \(i = 1\): \(S'[1..3] = \text{"bca"}\) - \(3\) characters from \(i = 2\): \(S'[2..4] = \text{"cab"}\)

In this way, we have reduced the circular problem to a standard string search problem: “find starting positions in string \(S'\) that match pattern \(T\).”

2. Naive approach and its limitations

For each starting position \(i\) (\(0 \leq i < N\)), naively comparing the substring \(S'[i \dots i+M-1]\) of the linearized \(S'\) with \(T\) takes \(O(M)\) in the worst case per comparison. The total time complexity becomes \(O(NM)\), and with the constraints \(N, M \leq 5 \times 10^5\), this requires up to approximately \(2.5 \times 10^{11}\) operations in the worst case, which will not meet the time limit (TLE).

3. Speedup using Z-algorithm

To perform string pattern matching efficiently, we use the Z-algorithm. The Z-algorithm computes, for a given string \(U\), the length of the longest common prefix between \(U\) and the substring starting at each position \(k\), for all \(k\), in \(O(|U|)\) time.

To utilize this, we construct a new string \(U\) as follows: $\(U = T + \text{"\#"} + S'\)\( Here, `"#"` is a special character (delimiter) that does not appear in \)S\( or \)T$.

Applying the Z-algorithm to this string \(U\) gives us the array \(Z\). In \(U\), \(S'\) starts from index \(M+1\) onwards. For each \(i\) (\(0 \leq i < N\)), the index in \(U\) corresponding to starting position \(i\) in the original \(S\) is \(M + 1 + i\). If \(Z[M + 1 + i] \geq M\), then the substring starting at that position matches \(T\) for at least \(M\) characters (= it completely matches \(T\)).

---

Algorithm

Let’s trace through the process with the concrete example \(S = \text{"abc"}\) (\(N=3\)), \(T = \text{"cab"}\) (\(M=3\)).

1. Creating the extended string \(S'\) Set the length of \(S'\) to \(N + M - 1 = 5\), and append \(S[i \bmod N]\) sequentially. This gives \(S' = \text{"abcab"}\).

2. Creating the search string \(U\) Concatenate \(T\), the delimiter "#", and \(S'\). This gives \(U = \text{"cab\#abcab"}\) (length \(9\)).

3. Applying the Z-algorithm The Z-algorithm result (array \(Z\)) for string \(U\) is as follows:

| Index \(k\) | \(U[k]\) | \(U[k:]\) | Match length with prefix \(U = \text{"cab..."}\): \(Z[k]\) | | :—: | :—: | :— | :—: | | 0 | ‘c’ | "cab#abcab" | 9 | | 1 | ‘a’ | "ab#abcab" | 0 | | 2 | ‘b’ | "b#abcab" | 0 | | 3 | ‘#’ | "#abcab" | 0 | | 4 (\(i=0\)) | ‘a’ | "abcab" | 0 | | 5 (\(i=1\)) | ‘b’ | "bcab" | 0 | | 6 (\(i=2\)) | ‘c’ | "cab" | 3 (matches \(\text{"cab"}\)) | | 7 | ‘a’ | "ab" | 0 | | 8 | ‘b’ | "b" | 0 |

1. Judgment and counting Among \(i = 0, 1, 2\), the only case where \(Z[M + 1 + i] \geq M\) is \(i = 2\) (\(Z[6] = 3 \geq 3\)). Therefore, the number of matching starting positions is \(1\).

---

Complexity

• Time complexity: \(O(N + M)\)

  • Constructing string \(S'\) takes \(O(N + M)\) time.
  • The length of the constructed string \(U\) is \(N + 2M\). Since the Z-algorithm runs in linear time, its execution time is \(O(|U|) = O(N + M)\).
  • The judgment loop runs \(N\) times, which is \(O(N)\).
  • Overall, the complexity is \(O(N + M)\), which runs very fast (under 0.1 seconds) within the given constraints.

• Space complexity: \(O(N + M)\)

  • Memory of length \(O(N + M)\) is used to store the strings \(S', U\) and the array \(Z\) holding the Z-algorithm results.

---

Implementation Notes

• Handling the case \(M > N\) When \(M\) is larger than \(N\), the circle is traversed more than once. When constructing string \(S'\), by using the modulo operation (%) as in S[i % N], characters are automatically filled by looping around as many times as needed.

• Importance of the delimiter character The character inserted between \(T\) and \(S'\) (in this case "#") must be a character that does not appear in the input. Without it, matching could extend beyond the boundary of \(T\) into \(S'\), causing incorrect judgments.

• Pre-allocating memory (reserve) In C++, repeated concatenation of std::string can cause multiple memory reallocations, becoming a bottleneck. By calling S_prime.reserve(N + M) to pre-allocate memory, we achieve a constant-factor speedup.

  Source Code

#include <iostream>
#include <string>
#include <vector>
#include <atcoder/string>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string S, T;
    if (!(cin >> S >> T)) return 0;

    int N = S.length();
    int M = T.length();

    string S_prime = "";
    S_prime.reserve(N + M);
    for (int i = 0; i < N + M - 1; ++i) {
        S_prime += S[i % N];
    }

    string U = T + "#" + S_prime;
    vector<int> z = atcoder::z_algorithm(U);

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        if (z[M + 1 + i] >= M) {
            ans++;
        }
    }

    cout << ans << "\n";

    return 0;
}

---

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