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

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

每天一句叨叨

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

喂马、劈柴,周游世界

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

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

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

告诉他们我的幸福

那幸福的闪电告诉我的

我将告诉每一个人

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

陌生人,我也为你祝福

愿你有一个灿烂的前程

愿你有情人终成眷属

愿你在尘世获得幸福

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