首页 > 数据结构 > Hash表 > HDU 4821-String-字符串-[解题报告]HOJ
2015
09-18

HDU 4821-String-字符串-[解题报告]HOJ

String

问题描述 :

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.

输入:

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.

输出:

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.

样例输入:

3 3
abcabcbcaabc

样例输出:

2

闲来无事,刷道哈希。

将一个字符串看成一个数即可,如果是小写字母,31进制,所有字符,131进制,反正进制是大于字符种类数的素数,然后一个字符串就对应了唯一的一个值,注意,有可能出现前导0,这种情况下,将字符的值+1即可。

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#define ull unsigned long long

using namespace std;

int M,L;
char s[100010];
const int seed=31;
ull nbase[100010];
ull hash[100010];
ull h[100010];

void solve()
{
    int len=strlen(s+1);
    hash[len+1]=0;
    for (int i=len;i>=1;i--)
        hash[i]=hash[i+1]*seed+s[i]-'a';
    for (int i=1;i+L-1<=len;i++)
        h[i]=hash[i]-hash[i+L]*nbase[L];
    int ans=0;
    for (int i=1;i<=L&&i+L*M-1<=len;i++)
    {
        map <ull,int> mp;
        for (int t=0;t<M;t++)
        {
            ull hh=h[i+t*L];
            mp[hh]++;
        }
        if (mp.size()==M)
            ans++;
        for (int t=M;i+(t+1)*L-1<=len;t++)
        {
            ull hh=h[i+(t-M)*L];
            mp[hh]--;
            if(!mp[hh])
                mp.erase(hh);
            hh=h[i+t*L];
            mp[hh]++;
            if (mp.size()==M)
                ans++;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    nbase[1]=seed;
    for (int i=2;i<=100010;i++)
        nbase[i]=nbase[i-1]*seed;
    while (~scanf("%d%d",&M,&L))
    {
        scanf("%s",s+1);
        solve();
    }
}

参考:http://blog.csdn.net/u011663071/article/details/39586595