ICPC Regional 2023 L

#include <bits/stdc++.h>

using namespace std;

#define forr(i,l,r) for(int i=int(l);i<int(r);++i)
#define sz(c) (int((c).size()))

int longest_repetition(const string_view& word, const int d) {
    const int n = sz(word);
    vector<int> z = {0};
    int m = min(d, n), l = 0, r = 0;
    forr(i, 1, min(d + 1, n)) {
        z.push_back(0);
        if (i <= r) {z[i] = min(r - i + 1, z[i - l]);}
        while (i + z[i] < n && word[z[i]] == word[i + z[i]]) {++z[i];}
        if (i + z[i] - 1 > r) {l = i, r = i + z[i] - 1;}
        m = max(m, i + z[i]);
    }
    return m;
}

void solve() {
    string s;
    cin>>s;
    int d;
    cin>>d;
    string_view word = s;
    int ans = 0;
    while (!word.empty()) {
        ++ans;
        word.remove_prefix(longest_repetition(word, d));
    }
    cout<<ans<<'\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}