选用 BKDRhash 方式
参考资料:https://www.byvoid.com/blog/string-hash-compare/
字符串通篇资料:https://blog.csdn.net/ck_boss/article/details/47066727

HDU 4821 string

传送门:https://vjudge.net/problem/HDU-4821
题意:给出M和L,和一个字符串S。要求找出S的子串中长度为L*M,并且可以分成M段,每段长L,并且M段都不相同的子串个数。

思路:一道字符串哈希题。哈希的方法是BKDRHash,哈希中进制是31,131等素数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
	#include <iostream>
#include <map>
#include <string>
#include <cstring>
#include <cstdio>
#define maxn 100005
#define SEED 31
#define ULL unsigned long long
using namespace std;

ULL k[maxn],ha[maxn];
map <ULL , int> mp;
int m,l;
char s[maxn];
int main(){
while (scanf("%d%d",&m,&l)!=EOF){
scanf("%s",s);
k[0]=1;
int len = strlen(s);
ha[len] = 0;
for (int i=1;i<=l;i++)
k[i] = k[i-1]*SEED;
for (int i=len-1;i>=0;i--)
ha[i] = ha[i+1]*SEED + s[i] - 'a' + 1;
int ans=0;

for (int i=0;i<l && i+m*l<len;i++){
mp.clear();
for (int j=i;j<i+m*l;j+=l)
mp[ha[j]-ha[j+l]*k[l]]++;
if (mp.size() == m) ans++;
for (int j=i+m*l;j<=len-l;j+=l){
int head = j-m*l;
ULL x = ha[head] - ha[head+l]*k[l];
mp[x]--;
if (mp[x] == 0) mp.erase(x);
mp[ha[j] - ha[j+l]*k[l]]++;
if (mp.size() == m) ans ++;
}
}
cout << ans << endl;
}
}

HDU 4080 Stammering Aliens
题意
每组数据为一个整数m和一个长度不小于m的字符串,求该字符串的一个子串,该子串在满足出现次数不小于m的同时应尽量长。
输出该长度和最右侧出现的起始位置。如果存在多组数据,输出有最靠近右侧的那组。
m<=4e5,时限5s


字符串hash+二分答案。我写的版本被卡了,从网上找了一个相同写法的4000ms卡过去了,学习一下。
by Vicente:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstring>
#include <iostream>
#include <map>
#define maxn 40005
#define SEED 31
#define ULL unsigned long long
using namespace std;
int m,len;
ULL k[maxn],ha[maxn];
char s[maxn];
map <ULL , int> mp;

bool isOK(int L){
mp.clear();
for (int i=0;i+L<=len;i++){
mp[ha[i]-ha[i+L]*k[L]]++;
if (mp[ha[i] - ha[i+L]*k[L]]>=m)return true;
}
return false;
}
int main(){
while (scanf("%d",&m) && m!=0){
scanf("%s",s);
len = strlen(s);
k[0] = 1;
for (int i=1;i<=len;i++) k[i] = k[i-1] * SEED;
ha[len] = 0;
for (int i = len-1;i>=0;i--) ha[i] = ha[i+1] * SEED + s[i] - 'a'+1;
int l=m,r=len,mid;
while (l<r){
mid = (l+r+1) >>1;
if (isOK(mid)) l = mid;else r=mid-1;
}

if (!isOK(r)) {
puts("none");
continue;
}else{
cout << r << " ";
mp.clear();
for (int i=0;i+r<=len;i++){
mp[ha[i]-ha[i+r]*k[r]]++;
if (mp[ha[i] - ha[i+r]*k[r]]>=m) cout << i << endl;
}
}
}
}

AC版本:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <cstring>
#include <iostream>
#include <map>
#define ull unsigned long long
using namespace std;
const int maxn = (int)4e4 + 10;
int n,len;
char s[maxn];
ull has[maxn];
ull p = 2333,a[maxn];

bool judge(int x)
{
map<int,int> mp;
ull res;
for (int i = 1;i + x - 1 <= len;i ++)
{
res = has[i + x - 1] - has[i - 1] * a[x];
if (++mp[res] >= n) return 1;
}
return 0;
}
int check(int x)
{
map<int,int> mp;
int pos = -1;
ull res;
for (int i = 1;i + x - 1 <= len;i ++)
{
res = has[i + x - 1] - has[i - 1] * a[x];
if (++mp[res] >= n) pos = i;
}
return pos - 1;
}
int main()
{
while (~scanf("%d",&n) && n)
{
scanf("%s",s + 1);
len = strlen(s + 1);
has[0] = 0,a[0] = 1;
for (int i = 1;i <= len;i ++)
{
has[i] = has[i - 1] * p + s[i];
a[i] = a[i - 1] * p;
}
int l = 1,r = len + 1,mid;
while (l <= r)
{
mid = (l + r) >> 1;
if (judge(mid)) l = mid + 1;
else r = mid - 1;
}
if (r == 0)
printf("none\n");
else
printf("%d %d\n",r,check(r));
}
return 0;
}

哈哈哈经过学习,我改了一点内容,终于也把这道题卡过去了。
在这里插入图片描述
4773ms…说是卡过去真是一点不错。
AC代码 by Vicente.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <cstring>
#include <iostream>
#include <map>
#define maxn 40005
#define SEED 31
#define ULL unsigned long long
using namespace std;
int m,len;
ULL k[maxn],ha[maxn];
char s[maxn];
map <ULL , int> mp;

bool isOK(int L){
mp.clear();
ULL res;
for (int i=0;i+L<=len;i++){
res=ha[i]-ha[i+L]*k[L];

if (++mp[res]>=m)return true;
}
return false;
}

int main(){
while (scanf("%d",&m) && m!=0){
scanf("%s",s);
len = strlen(s);
k[0] = 1;
ha[len] = 0;
for (int i=1;i<=len;i++)//强行放在一起写,就没爆T了
k[i] = k[i-1] * SEED,ha[len-i] = ha[len-i+1] * SEED + s[len-i] - 'a'+1;;
// for (int i = len-1;i>=0;i--) ha[i] = ha[i+1] * SEED + s[i] - 'a'+1;
int l=1,r=len+1,mid;

while (l<=r){
mid = (l+r) >>1;
if (isOK(mid)) l = mid+1;else r=mid-1;
}

if (r == 0) {
puts("none");
continue;
}else{
cout << r << " ";
mp.clear();
int x;
for (int i=0;i+r<=len;i++){
mp[ha[i]-ha[i+r]*k[r]]++;
if (mp[ha[i] - ha[i+r]*k[r]]>=m) x=i;//cout << i << endl;
}
cout << x << endl;//不用x标记的话会WA,原因自己想
}
}
}