首页 > 代码库 > HDU 5008西安网络赛B题:后缀数组求第k小子串

HDU 5008西安网络赛B题:后缀数组求第k小子串

思路:尼玛,这题搞了一天了,比赛的时候用了n^2的方法绝对T了,然后今天看别人代码看了一天才知道。后面感觉也挺容易的,就是没想到,之前做过SPOJ 694 705求过不同子串了,知道怎么求不同子串个数了,但是比赛的时候这个技巧竟然抛在脑后了,然后就不会了。

但是今天自己用了自己的两个后缀数组的模板(倍增和DC3)的都WA了,搞得自己真想跳楼去了!!

到现在都不知道到底是哪里错了,处理的方法和标准做法都一样,但是就是WA,然后用了别人的模板,再用自己的处理方法就过了,怀疑自己的两个模板是不是哪里错了,但是之前已经用这两个模板解决无数题了,真不知道哪里还有错的,fuck……无语……

每个后缀产生的不同子串个数就是:n-sa[i]-height[i],这个在SPOJ 694 705中解决过,不再说了。

然后第k小的肯定是从height[i]数组从前往后的,因为后缀已经按字典序排好了嘛,然后找第k个就行了。

现在找到的这个模板也挺快的,而且代码量还真短,速度又快,挺不错的……这个代码排在rank1了,328ms。

其实这题是随机数据,如果不是随机数据的话,我这代码是会T的,因为在倒数第九句那个是用while循环写的,试想如果数据是10^5个a的话,那个这个处理方法就每次都遍历到最后了,就是N^2的复杂度了,所以……正确的姿势应该是RMQ+二分,官方题解也是RMQ+二分,自己理解没错。本来刚开始用自己模板的时候我就是RMQ+二分做的,但是可能是模板原因WA了,然后就用的这个模板就再懒得写RMQ+二分了,因为网络赛数据太水了,比如这场网络赛的第三题,ACdream群上有个代码,数据水到这个代码连样例都没过都A了,真不知道数据啥样的。因为这种都是随机数据,所以YY咯。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const int N=111000;
char s[N]; // N>256
int n, sa[N], height[N], _rank[N], tmp[N], top[N];
void makesa() //O(N*logN)
{
    int i, j, len, na;
    na = (n < 256 ? 256 : n);
    memset(top, 0, na * sizeof(int));
    for (i = 0; i < n ; i++) top[ _rank[i] = s[i] & 0xff ]++;
    for (i = 1; i < na; i++) top[i] += top[i - 1];
    for (i = 0; i < n ; i++) sa[ --top[ _rank[i] ] ] = i;
    for (len = 1; len < n; len <<= 1)
    {
        for (i = 0; i < n; i++)
        {
            j = sa[i] - len;
            if (j < 0) j += n;
            tmp[ top[ _rank[j] ]++ ] = j;
        }
        sa[ tmp[ top[0] = 0 ] ] = j = 0;
        for (i = 1; i < n; i++)
        {
            if (_rank[ tmp[i] ] != _rank[ tmp[i-1] ] ||
                    _rank[ tmp[i]+len ]!=_rank[ tmp[i-1]+len ])
                top[++j] = i;
            sa[ tmp[i] ] = j;
        }
        memcpy(_rank, sa , n * sizeof(int));
        memcpy(sa , tmp, n * sizeof(int));
        if (j >= n - 1) break;
    }
}
void lcp() //O(4*N)
{
    int i, j, k;
    for (j = _rank[height[i=k=0]=0]; i < n - 1; i++, k++)
        while (k >= 0 && s[i] != s[ sa[j-1] + k ])
            height[j] = (k--), j = _rank[ sa[j] + 1 ];
}
ll f[N];
int main()
{
    while( scanf("%s", s)!=EOF )
    {
        n = strlen(s)+1;
        int len = n-1;
        makesa();
        lcp();
        int q;
        for(int i=1; i<=len; i++)
            f[i]=f[i-1]+len-sa[i]-height[i];
        ll k,v,l=0,r=0;
        scanf("%d",&q);
        while(q--)
        {
            scanf("%I64d",&v);
            k=(v^l^r)+1;
            if(f[len]<k)
            {
                l=r=0;
                puts("0 0");
                continue;
            }
            int pos=lower_bound(f+1,f+n,k)-f;
            l=sa[pos];
            //int len1;
            //if(pos) len1=k-f[pos-1]+height[pos];
            //else len1=k;
            int len1=len-(f[pos]-k)-l;
            while(++pos<n&&height[pos]>=len1)//这里最好用RMQ+二分,避免十万个a的数据的情况
                if(l>sa[pos]) l=sa[pos];
            l++;
            r=l+len1-1;
            printf("%I64d %I64d\n",l,r);
        }
    }
    return 0;
}


HDU 5008西安网络赛B题:后缀数组求第k小子串