HDU 4821 (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 line 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.

输出

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

输入样例

3 3

abcabcbcaabc

输出样例

2

解析

首先应明确一下题目中“don’t have the same character for every position”的含义，这其实就是说两个字符串不相同，即s1!=s2；并不是说两个字符串的任意两位都不同。

容易想到，我们可以将字符串S分割成若干个长度为L的子串，如，样例中的abcabcbcaabc可分割为：/abc/abc/bca/abc或a/bca/bcb/caa/bc或ab/cab/cbc/aab/c，共3种方案，我们以第一个子串的实际长度来区分这几种方案，则这3种方案可分别记作lstart=0, 1, 2。分割后我们可以分3种情况，对于每一种情况，从第一个子串开始扫描，处理到第M个子串时，判断已处理过的子串是否有重复，如果没有，则将答案加一，处理第M+1个子串时，可以考虑将第一个子串从“已处理的子串”中删除，以免重复处理。如此做，可以保证每个子串只被处理一次，而子串数等于S.length()-L+1，算法有可能在线性时间内实现。但存在以下难点：

1.        在O(1)或O(log₂n)的时间内判断两个字符串是否相等；

2.        在O(1)或O(log₂n)的时间内判断一个子串是否已被处理过。

第二个难点容易解决，只需用红黑树维护已处理过的字符串即可在O(log₂n)的时间内实现；而第一个难点的解决相对困难，我们需要在O(1)的摊还时间内获得一个子串的散列值。

（这里记S.length()=len）考虑预处理出以i开头长度为L的字符串的散列值，储存在全局数组hashes[100001]中。我们采用hash(S)=S[0]×33⁰+S[1]×33¹+S[2]×33²+…+S[len-1]×33^len-1（33可以替换成其他数字，但不保证替换后散列不会对撞）来计算字符串的散列。首先将33ⁱ预处理储存在数组exp[len]中，我们希望将hashes[i]表示成类似于hashes[i]-hash[i+L]这样的类似于后缀和的形式，于是我们令数组sum[i]=33*sum[i+1]+S[i]-97（’a’==97），而sum[L]=0。为了方便讲解我们以字符串abcabc为例：

S[i]	a	b	c	a	b	c
exp[i]	1	33	332	333	334	335
sum[i]	2×335+334+2×332+33	2×334+333+2×33+1	2×333+332+2	2×332+33	2×33+1	2
hashes[i]	33+2×332	1+2×33	2+332	33+2×332

观察发现hashes[i]实际上等于sum[i]-exp[L]*sum[i+L]。

评注：这种方法是计算字符串散列值的高效算法。

值得注意的是这一系列计算远超出了unsigned long long的范围，那么是否应该用高精度呢？答案是否定的：当CPU的运算器得到的结果超过了寄存器的宽度后，数字的高位将被舍去，这实际上相当于完成了一次取模运算，而a mod c-b mod c=(a-b) mod c (a, b, c ≥0)因此不必担心溢出的问题。

最终我们的算法的时间复杂度为O(nlog₂n+n)。

参考程序

#include <iostream>

#include <string>

#include <map>

using namespace std;

unsigned long long hashes[100001];

//预处理出所以长度为l的字符串的散列值 

void gethash(string &s,int l)

{

    int len=s.length();

    unsigned long long exp[len+1];

    exp[0]=1;

    for(int i=1;i<=len;i++)

    {

        exp[i]=exp[i-1]*33;

    }

    unsigned long long sum[len+1];

    sum[len]=0;

    for(int i=len-1;i>=0;i--)

    {

        sum[i]=33*sum[i+1]+s[i]-97;

    }

    for(int i=0;i<=len-l;i++)

    {

        hashes[i]=sum[i]-sum[i+l]*exp[l];

    }

}

int main()

{

    string str;

    int m,l,len,ans;

    //cnt[h]表示一个散列为h的字符串出现的次数

    //但cnt[h]的值均为1或0时，cnt.size()=m,

    //由此可判断每个子串是否只出现过一次 

    map <unsigned long long,int> cnt;

    while(cin>>m>>l)

    {

        cin>>str;

        len=str.length();

        ans=0;

        gethash(str,l);

        //枚举分割方案 

        for(int n=0;n<l&&n<=len-l*m;n++)

        {

            //cout<<"in case "<<n<<endl;

            cnt.clear();

            //sub表示已处理的子串的个数 

            int sub=0;

            //枚举这种方案下的子串

            //（通过枚举起始点实现） 

            for(int i=n;i<=len-l;i+=l)

            {

                cnt[hashes[i]]++;

                sub++;

                //cout<<"i="<<i<<" sub="<<sub<<endl;

                if(sub==m)

                {

                    //cout<<"sub==m cnt.size()="<<cnt.size()<<endl;

                    if(cnt.size()==m)

                    {

                        ans++;

                    }

                    //cout<<"i-l*m+l="<<i-l*m+l<<endl;

                    //将第一个处理子串从已处理的子串中去除，

                    //使已处理的子串的个数始终小于等于m

                    cnt[hashes[i-l*m+l]]--;

                    if(cnt[hashes[i-l*m+l]]==0)

                    {

                        cnt.erase(hashes[i-l*m+l]);

                    }

                    sub--;

                }

            }

        }

        cout<<ans<<endl;

    }

    return 0;

}