Overview

This problem asks us to select as many non-overlapping occurrences of pattern \(T\) within string \(S\) as possible, minimizing the total required time. It can be solved using pattern matching combined with a greedy algorithm.

Analysis

Key Insight

The total required time can be expressed as \(N - k(M-1)\) (where \(k\) is the number of times the discount pass is applied). Since \(N\) and \(M\) are fixed, we can see that to minimize the required time, we need to maximize \(k\) (the number of pass applications).

Reformulating the Problem

The intervals where the discount pass can be applied correspond to “starting positions of length-\(M\) substrings in \(S\) that match \(T\).” The problem becomes selecting as many non-overlapping intervals as possible from these intervals.

Thinking Through an Example

For example, if \(S = \) abcabcabc, \(T = \) abc (\(M=3\)): - Match positions (0-indexed): 0, 3, 6 - Intervals: \([0,2], [3,5], [6,8]\) - None of them overlap, so \(k=3\), and the answer is \(9 - 3 \times 2 = 3\)

Issues with a Naive Approach

Using dynamic programming (the general solution for interval scheduling) on all match positions would work since the number of matches is at most \(O(N)\), but an even simpler greedy approach yields the optimal solution.

Algorithm

Step 1: Pattern Matching (KMP Method)

Find all starting positions where \(T\) occurs in string \(S\). Using the KMP (Knuth-Morris-Pratt) algorithm, we can enumerate all match positions in \(O(N+M)\).

KMP procedure: 1. Construct the failure function for pattern \(T\) 2. Scan \(S\) from the beginning while tracking matches with \(T\), recording positions of complete matches

Step 2: Greedy Algorithm (Interval Scheduling Problem)

It is well known that the problem of “selecting the maximum number of non-overlapping intervals” can be optimally solved by a greedy algorithm that selects intervals in order of earliest ending position.

In this problem, since all intervals have the same length \(M\), matches are enumerated in order of earliest starting position. This is also the order of earliest ending position, so simply going from left to right and “selecting an interval if it doesn’t overlap with the previously selected interval” gives the maximum count.

Step 3: Computing the Answer

If \(k\) intervals were selected, the answer is \(N - k(M-1)\).

Special Case: When \(M = 1\)

When \(M = 1\), applying the discount pass doesn’t change the required time (\(1 \to 1\), savings \(= M-1 = 0\)), so the answer is always \(N\).

Complexity

• Time complexity: \(O(N + M)\) (dominated by KMP pattern matching)
• Space complexity: \(O(N + M)\) (for storing the failure function and match positions)

Implementation Notes

• When \(M = 1\), the savings is \(0\), so returning early avoids unnecessary computation

• In the KMP failure function, by setting k = fail[k-1] after a complete match, all match positions (allowing overlaps) can be enumerated without omission

• In the greedy algorithm, maintain last_end (the ending position of the last selected interval), and select a new interval if its starting position is greater than last_end

• Since \(N\) can be as large as \(10^6\), fast input using sys.stdin.buffer.read() is important in Python

  Source Code

import sys

def solve():
    input_data = sys.stdin.buffer.read().decode()
    tokens = input_data.split()
    N = int(tokens[0])
    M = int(tokens[1])
    S = tokens[2]
    T = tokens[3]
    
    if M == 1:
        # Every position where S[i] == T[0] saves 0 time (M-1=0), so answer is N
        # Actually M=1 means each match saves M-1=0, so answer is always N
        # Wait, if M=1, applying the pass to a single toll booth costs 1 instead of 1, no saving.
        print(N)
        return
    
    # Find all positions where T matches in S (0-indexed start positions)
    # Use KMP or rolling hash
    # Let's use KMP
    
    # Build KMP failure function for T
    m = len(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
    
    # Find all match positions (0-indexed)
    matches = []
    k = 0
    for i in range(N):
        while k > 0 and T[k] != S[i]:
            k = fail[k - 1]
        if T[k] == S[i]:
            k += 1
        if k == m:
            matches.append(i - m + 1)  # 0-indexed start
            k = fail[k - 1]
    
    if not matches:
        print(N)
        return
    
    # Now we need to select maximum number of non-overlapping intervals
    # Each interval is [matches[i], matches[i] + M - 1]
    # Greedy: pick the earliest ending interval, then the next one that doesn't overlap
    
    count = 0
    last_end = -1
    for start in matches:
        if start > last_end:
            count += 1
            last_end = start + M - 1
    
    print(N - count * (M - 1))

solve()

---

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