Overview

This problem asks us to find the maximum number of non-overlapping occurrences of a specific pattern \(T\) of length \(M\) within a string \(S\) of length \(N\), and then use that to calculate the minimum total travel time.

Analysis

1. Simplifying the Formula

Let \(k\) be the number of intervals where the discount pass is applied. The total travel time is expressed as \(N - k(M - 1)\). Since \(N\) and \(M\) are constants given as input, minimizing the total travel time reduces to maximizing the number of intervals \(k\) where the discount pass is applied.

2. Naive Approach and Its Challenges

We need to find all positions in \(S\) that match \(T\) and select the maximum number of them such that they do not overlap.

If we naively check whether each position in string \(S\) matches \(T\), each check takes up to \(O(M)\) time. Performing this check for all starting positions requires \(O(NM)\) total computation. Given the constraints \(N, M \leq 10^6\), this results in up to approximately \(10^{12}\) operations in the worst case, which exceeds the time limit (typically around 2 seconds), causing TLE (Time Limit Exceeded).

3. Efficient Solution

To solve this problem, we speed up the process by dividing it into the following two steps:

1. Fast String Searching: We use the KMP Algorithm (Knuth-Morris-Pratt Algorithm), which can enumerate all starting positions where \(T\) appears in \(S\) in \(O(N + M)\) time.
2. Maximizing Intervals (Interval Scheduling Problem): From the enumerated occurrence positions, we select the maximum number of non-overlapping intervals. This is known as the “Interval Scheduling Problem” and can be solved optimally in \(O(N)\) using a Greedy Algorithm. Since all intervals in this problem have equal length \(M\), we can simply greedily select non-overlapping intervals from left to right (in order of increasing starting index) to obtain the maximum count.

---

Algorithm

Step 1: Pattern Searching with KMP Algorithm

The KMP algorithm precomputes the “length of the longest proper prefix which is also a suffix” (construction of the LPS array), allowing it to skip unnecessary comparisons when a mismatch occurs. Using this, we store all starting indices where \(T\) appears in string \(S\) in ascending order in a list called matches.

Step 2: Interval Selection with Greedy Algorithm

Using the obtained matches, we find the maximum number \(k\) of non-overlapping intervals.

1. Initialize a variable last_end to \(-1\), which keeps track of the ending index of the last selected interval.
2. Iterate through each starting index idx in matches in order.
3. If idx > last_end, then this interval does not overlap with any previously selected interval.
   • Increment the interval count \(k\) by \(1\).
   • Update last_end to idx + M - 1, which is the ending index of the newly selected interval.
4. If there is overlap, skip this interval and proceed to the next index.

Step 3: Calculating the Minimum Travel Time

Using the obtained maximum interval count \(k\), compute and output the final answer \(N - k(M - 1)\).

---

Complexity

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

  • The KMP LPS array construction takes \(O(M)\), and the search process takes \(O(N)\).
  • The greedy interval selection processes the match results (at most \(N\) matches) with a single loop, so it is \(O(N)\).
  • Therefore, the overall time complexity is \(O(N + M)\), which runs sufficiently fast for the constraint of \(10^6\).

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

  • The KMP LPS array uses \(O(M)\) memory, and the array storing match positions uses at most \(O(N)\) memory.

---

Implementation Notes

• Corner case when \(M > N\): If the discount pass length \(M\) is greater than the highway length \(N\), there are no intervals where the discount pass can be applied. In this case, there is no need to perform any search; we can immediately output \(N\) and terminate.

• Fast I/O: Since \(N\) can be large, in C++ we disable synchronization between std::cin and std::cout (ios_base::sync_with_stdio(false); cin.tie(NULL);) to reduce the time spent on input/output.

  Source Code

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// Function to build the Longest Prefix Suffix (LPS) array for KMP
vector<int> buildLPS(const string& pat) {
    int m = pat.length();
    vector<int> lps(m, 0);
    int len = 0;
    int i = 1;
    while (i < m) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    return lps;
}

// KMP algorithm to find all starting indices of pattern in text
vector<int> kmpSearch(const string& pat, const string& txt) {
    int m = pat.length();
    int n = txt.length();
    vector<int> lps = buildLPS(pat);
    vector<int> matches;
    int i = 0; // index for txt
    int j = 0; // index for pat
    while (i < n) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == m) {
            matches.push_back(i - j);
            j = lps[j - 1];
        } else if (i < n && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
    return matches;
}

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N, M;
    if (!(cin >> N >> M)) return 0;

    string S, T;
    cin >> S >> T;

    if (M > N) {
        cout << N << "\n";
        return 0;
    }

    // Find all occurrences of T in S
    vector<int> matches = kmpSearch(T, S);

    // Greedy interval scheduling to find the maximum number of non-overlapping intervals
    long long k = 0;
    int last_end = -1;
    for (int idx : matches) {
        if (idx > last_end) {
            k++;
            last_end = idx + M - 1;
        }
    }

    // Calculate the minimum total time
    long long ans = (long long)N - k * (M - 1);
    cout << ans << "\n";

    return 0;
}

---

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