HDU5008详解_后缀数组_二分_RMQ_算法日常[17/100]

发表于 更新于 分类于 阅读次数：
HDU5008详解_后缀数组_二分_RMQ_算法日常 从明天起，做一个幸福的人(每天只玩半个小时的手机,让自己要么大屏高效,要么认真体验生活)

HDU5008

题目链接

VJ上面
hdu上面

题意

给一个串，q次查询里面第k大的字串，并且要求输出这个串最早出现的位置的左右下标值

题解

Tips:看不懂题解的话可以看题解下面的题解小细节(之所以在前面提示是因为小编经常看到一个东西自己想了半天，然后发现后面竟然有解释…所以感觉有点浪费时间，所以自己的博文应该防止自己陷入同样的坑)

解法一 无RMQ O(case*q*(log_(n)+n))

考虑找到第k小的子串，直接拿原串先构造后缀数组，统计一下第i个后缀有多少个不同的前缀num[i]（也就是在原串中有多少个不重复的子串），按sa排序后，这些连续出现的子串的字典序也是相同的，那么对num[i]求前缀和后就可以去二分一个位置，找到字典序第k小的子串出现的位置pos了(到这里解法二也要用)。这里找到的位置不一定是最靠左的(不理解可以看下面的题解分析)，所以还要在原串中找一下最左的位置，其实到了这里，直接向后，暴力遍历后面排名的串(不理解可以看下面的题解分析)，若串的最长的连续的height[i]>=目标子串长度，则维护min(L,l)就可以直接得到最小的答案

解法二 RMQ O(case*(n*log_(n)+q*log_(n)))

当然解法一在极限数组（例如10W个a）很可能会TLE的，所以我们来看更快的方法，以应对更高的要求，把平时的节俭(抠门)习惯在计算机上面发挥到极致

先像解法一前面部分一样确定了当前的位置pos，我们要做的就是在pos后面找个R，使得[pos,R]这个区间的height的最小值>=目标子串的长度，那么找R可以直接在[POS,n]中二分，由于我们的height数组并不是有序的，所以我们不能使用lower_bound,但是要应对多次询问，我们不能像解法一一样暴力了，所以可以使用RMQ，在case开始的时候用n*log_(n)进行预处理，然后在多次查询中享受O(1)带来的极致体验(节俭的生活就是如此地惬意),最后我们在[pos,R]区间再RMQ一下就得到最后的答案了。注意这里求区间的RMQ和求答案的RMQ是查询的两个数组，要分别初始化…

题解细节精讲QA

Q1: 为什么后面只要找pos后的后缀中的前缀，不用往前找？而且为什么不同的串是那样求出来的？
A:

首先是关于一个字符串有多少不同子串的问题，串由小到大排起序来应该是按照sa[i]的顺序排出来的产生的。

比如abbacd，排序出来的后缀是这样的
rank值i—对应的后缀sa[i]

　　1—abbacd　　　第一个串产生的6个前缀都是新的子串(a,ab,abb……)

　　2—acd　　　　　第二个串除了和上一个串的相同的前缀a(长度为1) 3-1=2 产生了2个子串

　　3—bacd　　　　　4-0=4

　　4—bbacd　　　　5-1=4

　　5—cd　　　　　　2－0=0

　　6—d　　　　　　　1－0=0

所以所有不同的前缀应该是(len-sa[i])-height[i]的和，即后缀串长(总串长减后缀起始位置)减去与上一个串的最长公共前缀，然后求和。
如果你不了解height数组—>建议看看学习后缀数组的小建议

然后我们可以观察到字串是按照排名过来的

a,ab,abb,abba,abbac,abbacd,ac,acd,b,ba,……

并且也可以观察到第k大的不同的串如果在多个位置出现，那么一定是在后面的串中出现，比如k=3,即abb只能在后面的串出现(在abba，abbac,abbacd中出现)–>所以只要在后面查找

主要原因是所有的不同的串都是每个后缀的前缀

Q2: 为什么我们找到的第一个不是最靠左的呢？
A:
这里可以举一个反例就解决了，而且其实我们在题解二也举了这个例子(10w个a),我们这里为了分析方便就举例给的串是aaa，那么
排名rank　　　　　对应的后缀串
1　　　　　　　　　　a(rank[1]=2,即是后缀2)
2　　　　　　　　　　aa
3　　　　　　　　　　aaa
因此我们就可以看到第一个找到的a不是位置上最左边的，反而是最右边的

AC代码

提交都是G++

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
typedef long long LL;
int sa[maxn],height[maxn],rank[maxn],t[maxn],t2[maxn],c[maxn];
int n;
char str[maxn];
int q;
LL sum[maxn];

void build_sa(int m,int n){
    int *x=t,*y=t2;
    for(int i=0;i<m;i++)c[i]=0;
    for(int i=0;i<n;i++)c[x[i]=str[i]]++;
    for(int i=1;i<m;i++)c[i]+=c[i-1];
    for(int i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
    for(int k=1;k<=n;k<<=1){
        int p=0;
        for(int i=n-k;i<n;i++)y[p++]=i;
        for(int i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;
        for(int i=0;i<m;i++)c[i]=0;
        for(int i=0;i<n;i++)c[x[y[i]]]++;
        for(int i=1;i<m;i++)c[i]+=c[i-1];
        for(int i=n-1;i>=0;i--)sa[--c[x[y[i]]]]=y[i];
        swap(x,y);
        x[sa[0]]=0;p=1;
        for(int i=1;i<n;i++)
            x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++);
        if(p>=n)break;
        m=p;
    }
}

void getheight(int n){
    int k=0;
    for(int i=1;i<=n;i++)::rank[sa[i]]=i;
    for(int i=0;i<n;i++){
        if(k)k--;
        int j=sa[::rank[i]-1];
        while(str[i+k]==str[j+k])k++;
        height[::rank[i]]=k;
    }
}

void process(){
    memset(sum,0,sizeof(sum));
    sum[1]=n-sa[1];
    for(int i=2;i<=n;i++)
        sum[i]=sum[i-1]+n-sa[i]-height[i];
}

void solve(){
    scanf("%d",&q);
    LL l=0,r=0;
    process();
    while(q--){
        LL v;
        scanf("%lld",&v);
        LL k=(l^r^v)+1;
        /*获取有第k排名的不同字符的起始位置(sum见process函数)*/
        int pos=lower_bound(sum+1,sum+1+n,k)-sum;
        /*因为每个串都是  后缀 所以sum[pos]-(k-1)就能得到第k个起始的后缀长度！
        然后用n减去,就是k起始的位置！
        (字符串下标从0开始,可以用k=1,来模拟理解一遍) */
        LL tl=sa[pos],tr=n-(sum[pos]-k+1);
        l=tl,r=tr;
        int len=tr-tl+1;
        while(pos+1<=n&&height[pos+1]>=len){
            pos++;
            tl=sa[pos],tr=tl+len-1;
            l=min(l,tl),r=min(r,tr);
        }
        l++,r++;
        if(pos>=n+1)l=r=0;
        cout<<l<<" "<<r<<endl;
    }
}

int main(){
    while(scanf("%s",str)!=EOF){
        n=strlen(str);
        build_sa(123,n+1);
        getheight(n);
        solve();
    }
    return 0;
}

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=205000;
char str[maxn];
int belong[maxn];
int s[maxn],rs[maxn];
int sa[maxn],t[maxn],t2[maxn],c[maxn];
int n,m,tt;
int rank[maxn],height[maxn];
int d[2][maxn][50];
int LOG[maxn];
ll num[maxn];
int len,l;
inline int idx(char c){ return c-'a'+1; }
inline char fdx(int x){ return char(x-1+'a'); }
void calheight(int n){
    int i,k=0;
    for (i=0; i<=n; i++) ::rank[sa[i]]=i;
    for (i=0; i<n; i++){
        if (k) k--;
        int j=sa[::rank[i]-1];
        while(s[i+k]==s[j+k]) k++;
        height[::rank[i]]=k;
    }
}

void da(int m,int n){
    n++;
    int i,*x=t,*y=t2;
    for (int i=0; i<m; i++) c[i]=0;
    for (int i=0; i<n; i++) c[x[i]=s[i]]++;
    for (int i=1; i<m; i++) c[i]+=c[i-1];
    for (int i=n-1; i>=0; i--)
      sa[--c[x[i]]]=i;
    for (int k=1; k<=n; k<<=1){
        int p=0;
        for (i=n-k; i<n; i++) y[p++]=i;
        for (i=0; i<n; i++) if (sa[i]>=k) y[p++]=sa[i]-k;

        for (i=0; i<m; i++) c[i]=0;
        for (i=0; i<n; i++) c[x[y[i]]]++;
        for (i=1; i<m; i++) c[i]+=c[i-1];
        for (i=n-1; i>=0; i--) sa[--c[x[y[i]]]] = y[i];
        swap(x,y);
        p=1;
        x[sa[0]]=0;
        for (i=1; i<n; i++)
        x[sa[i]]=(y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k])? p-1 : p++;
        if (p>=n) break;
        m=p;
    }
}

int RMQ_init(int x,int A[]){
    for(int i=1; i<=n; i++) d[x][i][0]=A[i];
    for (int j=1; (1<<j)<=n; j++)
        for (int i=1; i+(1<<j)-1<=n; i++)
            d[x][i][j]=min(d[x][i][j-1],d[x][i+(1<<(j-1))][j-1]);
    return 0;
}

int RMQ(int x,int L,int R){
    int k=LOG[R-L+1];
    return min(d[x][L][k],d[x][R-(1<<k)+1][k]);
}
int main(){
    int k=0;
    for (int i=0; i<105000; i++){
        while((1<<(k+1))<=i) k++;
        LOG[i]=k;
    }
    while(~scanf("%s",str)){
        int l=strlen(str);
        for(int i=0; i<l; i++) s[i]=idx(str[i]);
        n=l;
        s[n]=0;
        da(33,n);
        calheight(n);

        for (int i=0; i<=n; i++) num[i]=n-sa[i];
        for (int i=1; i<=n; i++) num[i]-=height[i];
        for (int i=1; i<=n; i++) num[i]+=num[i-1];
        ll tot=num[n];
        scanf("%d",&m);
        ll la=0,lb=0;
        ll k;
        /*d[0]存着height的rmq,d[1]存着sa的rmq*/
        RMQ_init(0,height);
        RMQ_init(1,sa);
        while(m--){
            scanf("%lld",&k);
            k=(k^la^lb)+1;
            if (k>=1 && k<=tot){
                int pos=lower_bound(num+1,num+1+n,k)-num;
                /*这个len求得很精致,k-(pos-1)位置起始的不同串的个数,
                这样就能得到k结束位置距离height结束位置的串长，加上height就是正好len*/
                int len=k-num[pos-1]+height[pos];
                int l=pos+1,r=n;
                int mid;
                int L=pos,R;
                /*二分右端点使得右边的最需最长公共字串是我们的k长串*/
                while(l<r){
                    mid=(l+r)>>1;
                    if (RMQ(0,pos+1,mid)>=len) l=mid+1;
                    else r=mid;
                }
                /*因为上面二分是mid+1,所以这里需要保险一下*/
                if (RMQ(0,pos+1,l)>=len) R=l; else R=l-1;
                /*所有地方求最小的sa*/
                la=RMQ(1,L,R);
                lb=la+len-1;la++;lb++;
                printf("%lld %lld\n",la,lb);
            }
            else la=lb=0,puts("0 0");
        }
    }
    return 0;
}

参考:
http://www.voidcn.com/article/p-xboamjdx-bg.html
https://www.cnblogs.com/chanme/p/4000976.html

每天一句叨叨

从明天起，做一个幸福的人(每天只玩半个小时的手机,让自己要么大屏高效,要么认真体验生活)

喂马、劈柴，周游世界

从明天起，关心粮食和蔬菜

我有一所房子，面朝大海，春暖花开

从明天起，和每一个亲人通信

告诉他们我的幸福

那幸福的闪电告诉我的

我将告诉每一个人

给每一条河每一座山取一个温暖的名字

陌生人，我也为你祝福

愿你有一个灿烂的前程

愿你有情人终成眷属

愿你在尘世获得幸福

我只愿面朝大海，春暖花开