HDU 4821 String 字符串HASH

本文主要是介绍HDU 4821 String 字符串HASH，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=4821

代码：

#include <bits/stdc++.h>
using namespace std;typedef unsigned long long ULL;
const int maxn = 100000 + 50;
const ULL seed = 131;
ULL HASH[maxn],BASE[maxn];
char str[maxn];
int main(){int m,l;BASE[0] = 1;for(int i = 1;i < maxn;++i) BASE[i] = BASE[i - 1] * seed;while(scanf("%d %d",&m,&l) != EOF){scanf("%s",str);int len = strlen(str);HASH[len] = 0;for(int i = len - 1;i != -1;--i) HASH[i] = HASH[i + 1] * seed + str[i] - 'a' + 1;map<ULL,int> mp;int ans = 0;for(int i = 0;i < l && i < len && i + m * l <= len;++i){//initmp.clear();for(int j = 0;j < m;++j){ULL tmp = HASH[j * l + i] - HASH[j * l + l + i] * BASE[l];mp[tmp]++;}if(mp.size() == m) ans++;//diedaifor(int j = m * l + i;j < len && j + l <= len;j += l){ULL tmp = HASH[j] - HASH[j + l] * BASE[l];mp[tmp]++;int tmp_p = j - m * l;tmp = HASH[tmp_p] - HASH[tmp_p + l] * BASE[l];mp[tmp]--;if(mp[tmp] == 0) mp.erase(tmp);if(mp.size() == m) ans++;}}printf("%d\n",ans);}
}

这篇关于HDU 4821 String 字符串HASH的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---