这两天做了几道题，跑来总结总结。
这道题到手先是读傻了。思来想去不得正解。百度了一下看到字符串Hash，立马关掉。又是一个陌生的术语。
找了些资料后先是做了poj1200，上手了字符串Hash。换句话说是BKDRHash。
简单的介绍一下。
unsigned int BKDRHash(char * str){
unsigned int base = 31; //131 1331 13331 ...
unsigned int hash = 0;
while (*str){
hash = hash*base + (*str++);
}
return hash;
}
这个函数可以把一个字符串转化成一个数字。
先去感受一下吧。
当你对BKDRHash有了一定概念以后。进入正文。
----------------------------------------------------------------------------------------------------------------------
遍历开头，也就是前L个字符。
然后把每L个字符转换成一个数字保存在数组中。
问题就转化成为求一个数组中连续的不相同的长度为m的子串。
用一个小技巧预处理一下可以让字符转化的复杂度降为O（n）。
求字符串前i个字符的Hash值。得到num[i]。
那么 i- j 对应的字符串所代表的数字为 num[j]-num[i]*p[j-i+1];
p为base对自己的累乘。不明白就看代码，一目了然。
问题传化后见变成了一个简单计数问题了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
typedef unsigned __int64 ULL;
const int N = 1e5 + 10;
char s[N];
ULL num[N];
ULL p[N];
int m, l;
map<ULL, int> mp;
ULL base = 31;
ULL t[N];
int cnt;
int main(){
p[0] = 1;
for (int i = 1; i < N; i++)
p[i] = p[i - 1] * base;
while (~scanf("%d%d%s", &m, &l, s)){
int len = strlen(s);
int i, j;
ULL Hash = 0;
//mp.clear();
memset(num,0,sizeof(num));
for (i = 1; i <= len ; ++i){
num[i] = num[i - 1] * base + s[i-1] - 'a';
}
int ml = m*l;
int ans = 0;
for (i = 0; i < l; ++i){
int tmp = 0;
cnt = 0;
for (j = i + 1; j + l - 1 <= len; j += l){
ULL Hash = num[j + l - 1] - num[j - 1] * p[l];
t[cnt++] = Hash;
/*// cout << Hash << endl;
if (mp[Hash] == false)
tmp++;
else{
mp.clear();
if (tmp >= m){
ans += tmp - m + 1;
tmp = tmp%m;
j -= tmp*l;
tmp = 0;
}
else tmp = 1;
}
mp[Hash] = true;
}
if (tmp >= m)ans += tmp - m + 1;
// cout << endl;*/
}
mp.clear();
for (j = 0; j < cnt; j++){
if (mp.find(t[j]) == mp.end())
{
mp[t[j]] = j;
tmp++;
}
else if (j - mp[t[j]] + 1 > m){
mp[t[j]] = j;
tmp++;
}
else if(tmp>=m){
ans += tmp - m + 1;
j = mp[t[j]];
tmp = 0;
mp.clear();
}
else{
j = mp[t[j]];
tmp = 0;
mp.clear();
}
}
if (tmp >= m){
ans += tmp - m + 1;
}
}
printf("%d\n" , ans );
}
return 0;
}
/*
3 3
qwertyuiopasqwefghjkl
*/