HDU-4821-String-hash-map

太过爱你忘了你带给我的痛 2022-04-22 02:06 167阅读 0赞

--------------------

## title: HDU 4821 String --hash+map   date: 2018-10-30 10:30:03   categories: “算法”   tag:   \- ACM   \- map   \- hash ##

题意：

给上限为1e5的字符串，找出有多少长度为M\*L的子串，并且该子串的M个长度为L的子串各不相同。

思路：

开始认为子串不想同的定义是每个位置的字符不相同，感觉说的有歧义。

> two strings are considered as “diversified” if they don’t have the same character for every position.

最暴力的算法就是枚举所有长度为M\*L的子串，判断hash子串是否合格。但是枚举子串是n^2的时间复杂度。可以仔细想一下，我们可以从下标1~L枚举起点，然后以这个起点用指针每次跳L步长。然后跟尺取原理似的一直保持map里的元素是M个。这样时间复杂度是O（L\*n/L）,即O(n)。为什么用map去重而不用set，原因就是对于相同的我们记住它出现了几次，只有他出现的次数==0的时候才将它删去。

#include<bits/stdc++.h>
    using namespace std;
    typedef unsigned long long ull;
    const int N=1e5+10;
    
    ull base[N], _hash[N], mul=37;
    char str[N];
    
    inline ull hash_str(int l, int r){
        return _hash[r]-_hash[l-1]*base[r-l+1];
    }
    
    int main(){
        int M, L;
        while(~scanf("%d%d", &M, &L)){
            scanf("%s", str+1);
            int len=strlen(str+1);
            base[0]=1;
            _hash[0]=0;
            for(int i=1; i<=len; i++){
                base[i]=base[i-1]*mul;
                _hash[i]=_hash[i-1]*mul+str[i];
            }
            map<ull, int> mp;
    
            int ans=0;
            for(int i=1; i<=L; i++){//enum start point
                mp.clear();
    
                for(int j=i; i+M*L-1<=len && j+L-1<=len; j+=L){
                    if(j-M*L>=i){
                        ull tmp=hash_str(j-M*L, j-M*L+L-1);
                        mp[tmp]--;
                        if(mp[tmp]==0) mp.erase(tmp);
                    }
                    mp[hash_str(j, j+L-1)]++;
                    if(mp.size()==M) ans++;
                }
            }
    
            printf("%d\n", ans);
    
        }
    
        return 0;
    }