概要

本問題は、長さ \(N\) の文字列 \(S\)（料金所の識別コード）から、長さ \(M\) の特定のパターン文字列 \(T\)（割引パス）を互いに重なり合わないように最大で何個切り出せるかを求め、それをもとに最小の合計所要時間を計算する問題です。

考察

1. 合計所要時間の数式を整理する

割引パスを \(k\) 回適用したとき、合計所要時間は \(N - k(M - 1)\) と表されます。 \(N\) と \(M\) は定数なので、この値を最小化するためには、割引パスの適用回数 \(k\) を最大化することに帰着されます。

2. 貪欲法の正当性

「重なり合わないようにパターン \(T\) を最大で何個選べるか」という問題は、区間スケジューリング問題に似ています。 文字列 \(S\) を左から右へ見ていき、パターン \(T\) と一致する箇所が見つかったら、即座にその区間を確定させて、次の文字から探索を再開する（貪欲法）のが最適です。

例えば、\(S = \text{"aaaa"}\)、\(T = \text{"aa"}\) の場合を考えます。 - 貪欲に選ぶ場合: \(1\) 文字目から \(2\) 文字目の \(\text{"aa"}\) を選び、次に \(3\) 文字目から \(4\) 文字目の \(\text{"aa"}\) を選ぶことで、計 \(2\) 個選べます。 - 貪欲に選ばない場合: もし \(2\) 文字目から \(3\) 文字目の \(\text{"aa"}\) を選んでしまうと、他の \(\text{"aa"}\) と重なってしまい、計 \(1\) 個しか選べなくなります。

したがって、左から順に見ていってマッチした時点で区間を確定させることが、その後の選択肢を最も多く残すことになり、最適解を導きます。

3. 高速な文字列マッチングの必要性

素朴にすべての位置から \(T\) との一致を判定すると、最悪の場合 \(O(NM)\) の計算量がかかってしまいます。本問題では \(N, M \le 10^6\) であるため、これでは実行時間制限に間に合いません（TLEとなります）。 そこで、文字列検索を高速に行うアルゴリズムである KMP法（Knuth-Morris-Pratt Algorithm） を使用します。

アルゴリズム

KMP法を用いることで、文字列 \(S\) の中からパターン \(T\) を \(O(N + M)\) の時間計算量で探索できます。

Step 1: KMPテーブル（ずらし表）の構築

パターン \(T\) の中で、「接頭辞（prefix）と接尾辞（suffix）がどこまで一致しているか」を事前に計算し、テーブル（配列）に保存します。 これにより、マッチング中に文字が不一致（ミスマッチ）となった際、パターンの先頭から比較をやり直すのではなく、一致していることが分かっている部分をスキップして効率的に比較を再開できます。

Step 2: 貪欲法を組み合わせたマッチング

文字列 \(S\) のインデックスを \(i\)、パターン \(T\) のインデックスを \(j\) として、左から順に文字を比較していきます。

1. \(S[i]\) と \(T[j]\) が一致する場合：
   • 両方のインデックスを \(1\) 進めます（i += 1, j += 1）。
   • もし \(j == M\)（パターン \(T\) がすべてマッチした）となった場合：
     • カウント \(k\) を \(1\) 増やします。
     • 重要: 今回は重複してパスを適用できないため、マッチした区間を完全に消費します。したがって、\(j\) を \(0\) にリセットし、重なりを防いだ状態で次の文字から新たな探索を開始します。
2. 不一致の場合：
   • \(j > 0\) であれば、KMPテーブルを参照して \(j\) を戻し、比較を継続します。
   • \(j == 0\) であれば、これ以上戻せないので \(i\) を \(1\) 進めます。

Step 3: 最小所要時間の計算

最終的に得られた最大適用回数 \(k\) を用いて、最小所要時間 \(N - k(M - 1)\) を出力します。

計算量

• 時間計算量: \(O(N + M)\)
  • KMPテーブルの構築に \(O(M)\)、文字列 \(S\) の走査に \(O(N)\) かかります。ポインタ \(i, j\) の移動回数は全体で線形に抑えられるため、全体として非常に高速に動作します。
• 空間計算量: \(O(M)\)
  • パターン \(T\) の情報を格納するKMPテーブル（サイズ \(M\) の配列）に必要なメモリ量です。

実装のポイント

• 重なりを防ぐリセット処理: 通常のKMP法では、パターンがマッチした後に「次のマッチング（重なりあり）」に備えてテーブルの値を元に \(j\) を更新しますが、本問題では重複を避けるために \(j = 0\) に強制リセットする必要があります。この処理により、一度割引パスに使われた文字が次の割引パスに再利用されるのを防いでいます。

  ソースコード

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

---

この解説は gemini-3.5-flash-thinking によって生成されました。