「HDU-4821」String(字符串hash)

发表于 | 分类于 ，

「HDU-4821」String
字符串hash，求长度为m*l子串中m个小子串两两互不完全相同的子串个数

*假的字符串选手发现自己甚至不会hash，学习一个。

题意

给定一个字符串，求将长度为m*l的子串分割为每段长度为l的m段后，m段两两互不完全相同的子串个数。

思路

对字符串求hash值，map计数去重，判断当前不同字符串数是否等于m.

对于每个中间区间相同的区间，利用滑动窗口求解降低复杂度，即：删除左侧子串哈希值，将右边区间哈希值加入集合。

代码

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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>

using namespace std;
typedef unsigned long long ull;

const int maxn=1e5+10;
const int seed=31;

ull base[maxn],h[maxn];
map <ull,int> hashmap;
char s[maxn];

ull gethash(int l,int r) {return h[r]-h[l-1]*base[r-l+1]; }

int main()
{
    int m,l,len;
    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",s+1);
        len=strlen(s+1);
        for(int i=1;i<=len;i++)
            h[i]=h[i-1]*seed+s[i]-'a';
        int cnt=0;
        for(int i=1;i<=l&&i+m*l<=len;i++)
        {
            hashmap.clear();
            for(int j=i;j<i+m*l;j+=l)
                hashmap[gethash(j,j+l-1)]++;
            if(hashmap.size()==m) cnt++;
            for(int j=i;j<=len-m*l-l+1;j+=l)
            {
                ull tmp=gethash(j,j+l-1);
                hashmap[tmp]--;
                if(!hashmap[tmp]) hashmap.erase(tmp);
                hashmap[gethash(j+m*l,j+m*l+l-1)]++;
                if(hashmap.size()==m) cnt++;
            }
        }
        printf("%d\n",cnt);
    }
    return 0;
}