[后缀数组][二分]hdu 5008

大致题意：

    给出一个长度小于100000的字符串，求字符串中字典序排在第k位的子串。

 

大致思路

    联动ural1590 http://bbezxcy.iteye.com/blog/1457009

   这里有一个后缀数组的基本规律，每个后缀去掉重复的前缀之后留下的就是所有的子串。

eg字符串 aabb 排列成后缀数组之后，|代表height计算出的和sa[i-1]相同的部分

 

sa[1]=0    aabb    子串有 aa aab aabb

sa[2]=1    a|bb     子串有 a ab abb

sa[3]=3    b          子串有 b

sa[4]=2    b|b       子串有 bb

 

先二分查找第k个子串大致在第几个sa(注意“大致”)，然后向下扫描heigt值小于子串长度lth且sa值最小的子串

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int Max = 100004;

int  num[Max];
int sa[Max], rank[Max], height[Max];
int wa[Max], wb[Max], wv[Max], wd[Max];

int cmp(int *r, int a, int b, int l){
    return r[a] == r[b] && r[a+l] == r[b+l];
}

void da(int *r, int n, int m){          //  倍增算法 r为待匹配数组  n为总长度 m为字符范围
    int i, j, p, *x = wa, *y = wb, *t;
    for(i = 0; i < m; i ++) wd[i] = 0;
    for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++;
    for(i = 1; i < m; i ++) wd[i] += wd[i-1];
    for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i;
    for(j = 1, p = 1; p < n; j *= 2, m = p){
        for(p = 0, i = n-j; i < n; i ++) y[p ++] = i;
        for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j;
        for(i = 0; i < n; i ++) wv[i] = x[y[i]];
        for(i = 0; i < m; i ++) wd[i] = 0;
        for(i = 0; i < n; i ++) wd[wv[i]] ++;
        for(i = 1; i < m; i ++) wd[i] += wd[i-1];
        for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i];
        for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){
            x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++;
        }
    }
}

void calHeight(int *r, int n){           //  求height数组。
    int i, j, k = 0;
    for(i = 1; i <= n; i ++) rank[sa[i]] = i;
    for(i = 0; i < n; height[rank[i ++]] = k){
        for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++);
    }
}

long long sub[Max];
int main(){
    char str[Max];
    int i, m=30, ans,len,n,h,lll,rrr;
    long long k,v;
    while(scanf("%s",str)!=EOF){
        len=strlen(str);
        for(i=0;i<=len;i++)num[i]=str[i]-'a'+1;
        num[len]=0;
        da(num, len + 1, m);
        calHeight(num, len);
        scanf("%d",&n);
        sub[0]=0;
        height[len+1]=0;
        for(i=1;i<=len;i++){
            sub[i]=(len-sa[i])-height[i];
            sub[i]+=sub[i-1];
          //  cout<<sub[i]<<" sub";
        }//cout<<endl;
        lll=rrr=0;
        while(n--){
            scanf("%I64d",&v);
            k=(lll^rrr^v)+1;
            //k=v;
            if(k>sub[len]){
                lll=0,rrr=0;
                printf("%d %d\n",lll,rrr);
                continue;
            }
            int low=1,high=len,mid,res=1;
            while(low<=high){
                mid=(low+high)/2;
                if(sub[mid]>=k){
                    res=mid;
                    high=mid-1;
                }else{
                    low=mid+1;
                }
            }//cout<<"res="<<res<<endl;
            lll=sa[res];
            //rrr=len-(sub[res]-k+1);
            rrr=lll+height[res]+k-sub[res-1]-1;
            //rrr=lll+height[lll]+k-sub[res]+1;
            int lth=rrr-lll+1;
           // cout<<"init"<<lll<<" "<<rrr<<" "<<lth<<endl;
            while(res+1<=len&&height[res+1]>=lth){
                res++;
                int tmpl=sa[res],tmpr=sa[res]+lth-1;
                lll=min(lll,tmpl);
                rrr=min(rrr,tmpr);
            }//rrr=lll+lth-1;
            lll++;
            rrr++;
            printf("%d %d\n",lll,rrr);
        }
    }
    return 0;
}