首页 > 代码库 > HDU 4821 杭州现场赛：每个片段字符串哈希比较

HDU 4821 杭州现场赛：每个片段字符串哈希比较

2024-07-13 12:29:52   227人阅读

I - String
Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u
Submit Status Practice HDU 4821

Description

Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if 
  (i) It is of length M*L; 
  (ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position. 

Two substrings of S are considered as “different” if they are cut from different part of S. For example, string "aa" has 3 different substrings "aa", "a" and "a". 

Your task is to calculate the number of different “recoverable” substrings of S.
 

Input

The input contains multiple test cases, proceeding to the End of File. 

The first line of each test case has two space-separated integers M and L. 

The second ine of each test case has a string S, which consists of only lowercase letters. 

The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.
 

Output

For each test case, output the answer in a single line.
 

Sample Input

 3 3
abcabcbcaabc
 

Sample Output

 2

思路：这题周赛的时候没做出来，有点可惜了。要是当时记起来unsigned long long自动取模，然后提醒一下大帝的话，兴许大帝就能过了。唉，导致让他取了好多个模，最后还是WA了。太不机智了。范逗了。

这题我是从前面哈希的，看到题解中从后面哈希，就是不爽，所以自己从前面哈希。其实都一样啦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<bitset>
#define INF 100007
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
char s[100005];
ull base[100010],hash[100010];
int main()
{
    int m,l,i,j;//system("pause");
    for(i=1,base[0]=1;i<100001;i++)
        base[i]=base[i-1]*131ULL;
    while(~scanf("%d%d",&m,&l))
    {
        map<ull,int>mm;
        scanf("%s",s);
        int sum=0,len=strlen(s);
        for(i=1,hash[0]=0;i<=len;i++)
            hash[i]=hash[i-1]*131+s[i-1]-'a'+1;
        for(i=0;i<l&&i+m*l<=len;i++)
        {
            mm.clear();
            for(j=i;j<m*l+i;j+=l)
                mm[hash[j+l]-hash[j]*base[l]]++;
            if(mm.size()==m) sum++;
            for(j=m*l+i;j<=len-l;j+=l)
            {
                int head=j-m*l;
                mm[hash[head+l]-hash[head]*base[l]]--;
                if(mm[hash[head+l]-hash[head]*base[l]]==0)
                    mm.erase(hash[head+l]-hash[head]*base[l]);
                mm[hash[j+l]-hash[j]*base[l]]++;
                if(mm.size()==m) sum++;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}



联系
我们