Overview

This problem asks us to find the maximum number of non-overlapping occurrences of a specific pattern string \(T\) (discount pass) of length \(M\) that can be extracted from a string \(S\) (toll booth identification code) of length \(N\), and then use that to calculate the minimum total travel time.

Analysis

1. Simplifying the Total Travel Time Formula

When the discount pass is applied \(k\) times, the total travel time is expressed as \(N - k(M - 1)\). Since \(N\) and \(M\) are constants, minimizing this value reduces to maximizing the number of discount pass applications \(k\).

2. Correctness of the Greedy Approach

The problem of “selecting the maximum number of non-overlapping occurrences of pattern \(T\)” is similar to the interval scheduling problem. Scanning string \(S\) from left to right and immediately fixing the interval whenever a match with pattern \(T\) is found, then resuming the search from the next character (greedy approach) is optimal.

For example, consider the case where \(S = \text{"aaaa"}\) and \(T = \text{"aa"}\). - Greedy selection: Select \(\text{"aa"}\) from position 1 to 2, then select \(\text{"aa"}\) from position 3 to 4, giving a total of \(2\) matches. - Non-greedy selection: If we select \(\text{"aa"}\) from position 2 to 3, it overlaps with other possible \(\text{"aa"}\) matches, and we can only select \(1\) in total.

Therefore, fixing an interval as soon as a match is found while scanning from left to right leaves the most options for subsequent selections, leading to the optimal solution.

3. Need for Fast String Matching

Naively checking for a match with \(T\) at every position results in a worst-case time complexity of \(O(NM)\). Since \(N, M \le 10^6\) in this problem, this would exceed the time limit (TLE). Therefore, we use the KMP Algorithm (Knuth-Morris-Pratt Algorithm), which performs string searching efficiently.

Algorithm

Using the KMP algorithm, we can search for pattern \(T\) within string \(S\) in \(O(N + M)\) time complexity.

Step 1: Building the KMP Table (Failure Function)

We precompute for pattern \(T\) how far the “prefix and suffix match” at each position, and store this in a table (array). This allows us, when a mismatch occurs during matching, to skip the portion that is already known to match rather than restarting the comparison from the beginning of the pattern, enabling efficient resumption of comparisons.

Step 2: Matching Combined with the Greedy Approach

Let \(i\) be the index for string \(S\) and \(j\) be the index for pattern \(T\). We compare characters sequentially from left to right.

1. If \(S[i]\) and \(T[j]\) match:
   • Advance both indices by 1 (i += 1, j += 1).
   • If \(j == M\) (the entire pattern \(T\) has been matched):
     • Increment the count \(k\) by 1.
     • Important: Since passes cannot be applied with overlap, we fully consume the matched interval. Therefore, we reset \(j\) to \(0\) and start a new search from the next character with no overlap.
2. If there is a mismatch:
   • If \(j > 0\), refer to the KMP table to move \(j\) back and continue comparison.
   • If \(j == 0\), we cannot move back further, so advance \(i\) by 1.

Step 3: Calculating the Minimum Travel Time

Using the maximum number of applications \(k\) obtained, output the minimum travel time \(N - k(M - 1)\).

Complexity

• Time Complexity: \(O(N + M)\)
  • Building the KMP table takes \(O(M)\), and scanning string \(S\) takes \(O(N)\). The total number of movements of pointers \(i\) and \(j\) is bounded linearly, so the overall algorithm runs very efficiently.
• Space Complexity: \(O(M)\)
  • This is the memory required for the KMP table (an array of size \(M\)) that stores information about pattern \(T\).

Implementation Notes

• Reset Processing to Prevent Overlap: In the standard KMP algorithm, after a pattern match, \(j\) is updated using the table value to prepare for the “next match (with overlap).” However, in this problem, \(j\) must be forcibly reset to \(0\) to avoid overlap. This processing prevents characters that were already used for one discount pass from being reused for the next discount pass.

  Source Code

import sys


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

    if M > N:
        print(N)
        return

    # KMPテーブルの構築
    table = [0] * M
    j = 0
    for i in range(1, M):
        while j > 0 and T[i] != T[j]:
            j = table[j - 1]
        if T[i] == T[j]:
            j += 1
        table[i] = j

    # 貪欲法によるマッチング
    k = 0
    j = 0
    i = 0
    while i < N:
        if S[i] == T[j]:
            i += 1
            j += 1
            if j == M:
                k += 1
                j = 0  # 重複を避けるため、マッチしたらjをリセット
        else:
            if j > 0:
                j = table[j - 1]
            else:
                i += 1

    ans = N - k * (M - 1)
    print(ans)


if __name__ == "__main__":
    solve()

---

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