You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
50 lines
1.2 KiB
Plaintext
50 lines
1.2 KiB
Plaintext
#include <cstdio>
|
|
#include <cstring>
|
|
#include <map>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
typedef unsigned long long ull;
|
|
const int N=1e5+50;
|
|
char str[N];
|
|
ull h[N],b[N];
|
|
map<ull,int> m;
|
|
ull gethash(int l,int r)
|
|
{
|
|
return h[r] - h[l-1]*b[r-l+1];
|
|
}
|
|
int main()
|
|
{
|
|
b[0]=1;
|
|
for(int i = 1; i < N; i++)
|
|
b[i] = b[i-1]*31;
|
|
int M,L;
|
|
while(~scanf("%d%d%s",&M,&L,str+1))
|
|
{
|
|
int len=strlen(str+1),ans=0;
|
|
h[0]=0;
|
|
for(int i=1; i<=len; i++)
|
|
h[i] = h[i-1]*31+ s[i] - 'a';
|
|
int lmt=min(l,len-M*L);
|
|
for(int i = 1; i <= lmt; i++)
|
|
{
|
|
m.clear();
|
|
for(int j = i; j < i + M*L ; j+=L)
|
|
m[gethash(j,j+l-1)]++;
|
|
if(m.size() == M)
|
|
ans++;
|
|
for(int j = i + M*lL; j + L-1 <= len; j += L)
|
|
{
|
|
ull x = gethash(j,j+L-1);
|
|
ull y = gethash(j-M*L,j-M*L+L-1);
|
|
m[x]++,m[y]--;
|
|
if(m[y] == 0)
|
|
m.erase(y);
|
|
if(m.size() == m)
|
|
ans++;
|
|
}
|
|
}
|
|
printf("%d\n",ans);
|
|
}
|
|
return 0;
|
|
}
|