## Editorial for Bedao Grand Contest 01 - DISTR

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#### 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;
}