文字列 \(S\) の中から文字列 \(T\) と一致する区間を重ならないようにしてできるだけ多く選ぶ問題です。このとき \(k\) 個の区間を選べると、問題文にある通り \(N-k(M-1)\) が答えとなります

文字列 \(S\) のうちの文字列 \(T\) と一致する区間は前から貪欲に取って行けばよいです。これはいわゆる区間スケジューリングと同じ貪欲法で、区間の幅が一定のため貪欲に先頭を前から埋めればよいだけです。

今度は、\(S\) のうち \(T\) と一致する区間を求めたいです。 これはRolling Hash, Z algorithm, KMP などを用いる様々な方法があります。この解説では Z algorithmを紹介します。

Z Algorithm 文字列 \(S\) が与えられたときに、 \(1 \leq i \leq |S|\) のすべての \(i\) について \(S\) と \(S[i:]\) の最大共通接頭辞の長さを 時間計算量 \(\mathrm{O}(|S|)\) で求めるアルゴリズムです。

この問題では、\(T+S\) を入力として Z algorithm で最大接頭辞の長さを求めて、\(T+S\) におけるインデックス \(i=M+1\) からスタートして\(S\) の各文字から始まる文字列が実際に \(T\) と一致するかを判定して貪欲に区間を選んで行けば良いです。

よって、時間計算量 \(\mathrm{O}(N+M)\) で解くことができます。

Z algorithm の詳細や実装は、AtCoder Libraryを参照してください。

実装例(C++)

#include <bits/stdc++.h>
#include <atcoder/string>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    string s, t;
    cin >> s >> t;
    string ts = t + s;
    vector<int> z = atcoder::z_algorithm(ts);
    int idx = m;
    int ans = 0;
    while (idx < n + m) {
        if (z[idx] >= m) {
            idx += m;
            ans++;
        }
        else{
            idx++;
            ans++;
        }
    }
    cout << ans << endl;
}