HDU 4821 字符串hash

题目大意:

希望找到连续的长为m*l的子串,使得m个l长的子串每一个都不一样,问能找到多少个这样的子串

简单的字符串hash,提前预处理出每一个长度为l的字符串的hash值

 #include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#include <set> using namespace std;
#define N 100010
#define base 31
typedef unsigned long long ULL;
map<ULL , int> _map;
int m , l;
ULL fac[N] , val[N];
char str[N]; void init()
{
fac[] = ;
for(int i= ; i<= ; i++) fac[i] = fac[i-]*base;
} int main()
{
#ifndef ONLINE_JUDGE
freopen("a.in" , "r" , stdin);
#endif // ONLINE_JUDGE
init();
while(~scanf("%d%d" , &m , &l))
{
scanf("%s" , str);
int len = strlen(str) , cnt , same , ret;
ULL cur = ;
for(int i= ; i<len ; i++){
if(i>=l) cur = cur-fac[l-]*str[i-l];
cur=cur*base+str[i];
if(i>=l-) val[i-l+] = cur;
//cout<<i-l+1<<" "<<val[i-l+1]<<endl;
}
ret=;
for(int i= ; i<l ; i++){
_map.clear();
cnt = , same = ;
for(int j=i ; j<len ; j+=l){
if(j+l->=len) break;
if(cnt >= m){
int la = j-m*l;
int t = _map[val[la]]--;
if(t==) same--;
}
int t = _map[val[j]]++;
if(t==) same++;
cnt++;
// cout<<j<<" "<<cnt<<" "<<endl;
if(cnt >= m && same==){
ret++;
// cout<<j<<endl;
} }
}
printf("%d\n" , ret);
}
return ;
}
上一篇:sqlserver 临时表、表变量、CTE的比较


下一篇:Python2字符编码问题汇总