http://acm.hdu.edu.cn/showproblem.php?pid=4821
题意:
给出一个字符串,现在问你可以找出多少个长度为M*L的子串,该子串被分成L个段,并且每个段的字符串都是不同的。
思路:
看BKDRHash看了半天,很神奇~。关于这个,大家可以看一下这篇博客http://blog.csdn.net/xu20082100226/article/details/52651072。
先计算出整个串的哈希值,套用公式$Hash[i]=Hash[i+1]*SEED+(ss[i]-'a'+1)$,这里SEED一般就是取个素数,Hash[i]表示第i个字符到终点的哈希值。然后枚举起点,由于一开始已经计算出了整个串的哈希值,所以长度为L的字符串的哈希值可以很容易的求出。用map来映射不同值出现的次数,如果mp.size()==M的话,那就说明这个子串是符合条件的。具体的一些说明可以看代码。
需要注意的是,由于hash的计算最后会使值很大,所以这里数据类型可以用usigned long long,可以自动取模。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 #include<set> 12 using namespace std; 13 typedef long long ll; 14 typedef pair<int,int> pll; 15 const int INF = 0x3f3f3f3f; 16 const int maxn = 100000+5; 17 18 const int SEED = 31; 19 20 char s[maxn]; 21 int M,L; 22 unsigned long long base[maxn]; 23 unsigned long long Hash[maxn]; 24 25 map<unsigned long long, int> mp; 26 27 int main() 28 { 29 //freopen("in.txt","r",stdin); 30 while(~scanf("%d%d",&M,&L)) 31 { 32 scanf("%s",s); 33 int len=strlen(s); 34 base[0]=1; 35 for(int i=1;i<=L;i++) 36 base[i]=base[i-1]*SEED; 37 Hash[len]=0; 38 for(int i=len-1;i>=0;i--) 39 Hash[i]=Hash[i+1]*SEED+(s[i]-'a'+1); 40 41 int ans=0; 42 for(int i=0;i<L && i+M*L<len;i++) //枚举字符串的起点 43 { 44 mp.clear(); 45 for(int j=i;j<i+M*L;j+=L) 46 { 47 mp[Hash[j]-Hash[j+L]*base[L]]++; 48 } 49 if(mp.size()==M) ans++; 50 51 for(int j=i+M*L;j<=len-L;j+=L) //滑动窗口 52 { 53 mp[Hash[j-M*L]-Hash[j-M*L+L]*base[L]]--; //去掉最左边的那一段长度L的字符串 54 if(mp[Hash[j-M*L]-Hash[j-M*L+L]*base[L]]==0) mp.erase(Hash[j-M*L]-Hash[j-M*L+L]*base[L]); //右边新加一段 55 mp[Hash[j]-Hash[j+L]*base[L]]++; 56 if(mp.size()==M) ans++; 57 } 58 } 59 printf("%d ",ans); 60 } 61 return 0; 62 }