Code mẫu

#include <bits/stdc++.h>
using namespace std;
#define maxn 10000007
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define checkfile(FiLeNaMe) { if(fopen(FiLeNaMe".inp","r")) freopen(FiLeNaMe".inp","r",stdin),freopen(FiLeNaMe".out","w",stdout); }
///mydata:
///>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
int n,k;
string s;
int a[maxn];
int z[maxn];

void prez(){
    z[1]=n;
    int l=0,r=0;

    forinc(i,2,n)
    if(r<i) { l=r=i; while(s[r]==s[r-l+1]) ++r; --r; z[i]=r-l+1; }
    else{
        int a=i-l+1,B=r-i+1;
        if(z[a]<B) z[i]=z[a];
        else { l=i; while(s[r]==s[r-l+1]) ++r; --r; z[i]=r-l+1; }
    }
}

void update(int i){
    if(i*k>n || z[i+1]<(k-1)*i) return;

    a[i*k]+=1;a[i*k+min(i,z[i*k+1])+1]-=1;
}

void enter(){
    cin>>n>>k;
    cin>>s;
    s='$'+s;
}

void solve(){
    prez();

    forinc(i,1,n/k) update(i);

    forinc(i,1,n) a[i]+=a[i-1];

    int ans=0;
    forinc(i,1,n) ans+=a[i]>0;

    cout<<ans;
}

signed main()
{
    checkfile("DISTR");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    enter();
    solve();

    return 0;
}