概要

文字列 \(S\) の中からパターン \(T\) と一致する部分を重ならないようにできるだけ多く選び、合計所要時間を最小化する問題です。パターンマッチング＋貪欲法で解けます。

考察

重要な気づき

合計所要時間は \(N - k(M-1)\) と表されます（\(k\) は割引パスを適用した回数）。\(N\) と \(M\) は固定なので、所要時間を最小化するには \(k\)（パスの適用回数）を最大化すればよいことがわかります。

問題の言い換え

割引パスを適用できる区間は「\(S\) の中で \(T\) と一致する長さ \(M\) の部分文字列の開始位置」に対応します。これらの区間から、互いに重ならないものをできるだけ多く選ぶ問題になります。

例で考える

例えば \(S = \) abcabcabc, \(T = \) abc (\(M=3\)) の場合： - マッチ位置（0-indexed）: 0, 3, 6 - 区間: \([0,2], [3,5], [6,8]\) - すべて重ならないので \(k=3\)、答えは \(9 - 3 \times 2 = 3\)

素朴なアプローチの問題

全マッチ位置に対して動的計画法（区間スケジューリングの一般解法）を使うと、マッチ数が最大 \(O(N)\) 個なのでそれでも間に合いますが、さらに単純な貪欲法で最適解が得られます。

アルゴリズム

ステップ1: パターンマッチング（KMP法）

文字列 \(S\) の中で \(T\) が出現するすべての開始位置を見つけます。KMP（Knuth-Morris-Pratt）法を使うことで、\(O(N+M)\) で全マッチ位置を列挙できます。

KMP法の手順： 1. パターン \(T\) の失敗関数（failure function）を構築する 2. \(S\) を先頭から走査しながら \(T\) とのマッチを追跡し、完全一致した位置を記録する

ステップ2: 貪欲法（区間スケジューリング問題）

「重ならない区間を最大個数選ぶ」問題は、終了位置が早い区間から順に選ぶ貪欲法で最適解が得られることが知られています。

本問題では、すべての区間の長さが同じ \(M\) なので、開始位置が早い順にマッチが列挙されます。これはそのまま終了位置が早い順でもあるため、前から順に「前回選んだ区間と重ならなければ選ぶ」とするだけで最大個数が求まります。

ステップ3: 答えの計算

\(k\) 個の区間を選べた場合、答えは \(N - k(M-1)\) です。

特殊ケース: \(M = 1\) の場合

\(M = 1\) のとき、割引パスを適用しても所要時間は \(1 \to 1\) で変わらない（節約 \(= M-1 = 0\)）ため、答えは常に \(N\) です。

計算量

• 時間計算量: \(O(N + M)\)（KMP法のパターンマッチングが支配的）
• 空間計算量: \(O(N + M)\)（失敗関数とマッチ位置の格納）

実装のポイント

• \(M = 1\) の場合は節約が \(0\) なので、早期リターンすると無駄な処理を省ける

• KMP法の失敗関数で、マッチ完了後に k = fail[k-1] とすることで、重なりを許した全マッチ位置を漏れなく列挙できる

• 貪欲法では last_end（最後に選んだ区間の終了位置）を管理し、新しい区間の開始位置が last_end より大きければ選択する

• \(N\) が最大 \(10^6\) と大きいため、Python では sys.stdin.buffer.read() による高速入力が重要

  ソースコード

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

---

この解説は claude4.6opus-thinking によって生成されました。