| Solved | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 5/17 | O | O | O | O | O | . | . | . | . | . | . | . | . | . | . | . | . |
- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet
最近在学习后缀数组，打一场练习。
密码：buaa
A
题目描述
求一个串的差分串的最长不重叠相同子串。
解题思路
唯一区别在于差分串导致的$jud$函数中$\geq$变为$>$。
AC代码
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
int s[N],n;
int x[N],y[N],c[N],sa[N],rank[N],height[N];
void getsa(){
int i,k,m=200;
n++;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=s[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1){
int num=0;
for(i=n-k;i<n;i++)y[num++]=i;
for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[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];
std::swap(x,y);
num=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]?num-1:num++;
if(num>=n)break;
m=num;
}
n--;
}
void getheight(){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(!rank[i]){
height[0]=k=0;
continue;
}
if(k)k--;
j=sa[rank[i]-1];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
int jud(int x){
int i,mn=1e9,mx=-1e9;
for(i=0;i<=n;i++){
if(height[i]<x)mn=mx=sa[i];
else{
mn=std::min(mn,sa[i]);
mx=std::max(mx,sa[i]);
if(mx-mn>x)return 1;
}
}
return 0;
}
int main(){
int i;
while(~scanf("%d",&n)&&n){
for(i=0;i<n;i++)scanf("%d",&s[i]);
for(i=0;i<n-1;i++)s[i]=s[i+1]-s[i]+90;s[n-1]=0;
getsa();getheight();
int l=0,r=n,ans=0;
while(l<r){
int mid=(l+r)>>1;
if(jud(mid))l=mid+1,ans=mid;
else r=mid;
}
if(ans>=4)printf("%d\n",ans+1);
else printf("0\n");
}
return 0;
}
B
题目描述
求一个串中最长的出现$k$次的可重叠子串。
解题思路
同样二分，每一个组的串个数$\geq k$即可。
AC代码
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
int s[N],n;
int x[N],y[N],c[N],sa[N],rank[N],height[N];
int k;
void getsa(){
int i,k,m=1000000;
n++;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=s[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1){
int num=0;
for(i=n-k;i<n;i++)y[num++]=i;
for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[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];
std::swap(x,y);
num=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]?num-1:num++;
if(num>=n)break;
m=num;
}
n--;
}
void getheight(){
int i,j,k=0;
for(i=1;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(!rank[i]){
height[0]=k=0;
continue;
}
if(k)k--;
j=sa[rank[i]-1];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
int jud(int x){
int i,num=0;
for(i=0;i<=n;i++){
if(height[i]<x)num=1;
else if(++num>=k)return 1;
}
return 0;
}
int main(){
int i;
while(~scanf("%d%d",&n,&k)&&n){
for(i=0;i<n;i++)scanf("%d",&s[i]);
getsa();getheight();
int l=0,r=n,ans=0;
while(l<r){
int mid=(l+r)>>1;
if(jud(mid))l=mid+1,ans=mid;
else r=mid;
}
printf("%d\n",ans);
}
return 0;
}
C
题目描述
求一个串中所有不同的子串。
解题思路
因为每一个子串都是某一个后缀的前缀，考虑加入每一个后缀的贡献。
每加入一个后缀$suffix(i)$，其与前面的重复的前缀个数为$height[i]$。于是答案为$\frac {n\times (n+1)}2 -\sum_{i=1}^{n}height[i]$。
AC代码
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
typedef long long ll;
char s[N];
int x[N],y[N],sa[N],c[10*N],rank[N],height[N],n;
void getsa(){
int i,k,m=10000;
n++;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=s[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1){
int num=0;
for(i=n-k;i<n;i++)y[num++]=i;
for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[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];
std::swap(x,y);
num=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]?num-1:num++;
if(num>=n)break;
m=num;
}
n--;
}
void getheight(){
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(!rank[i]){
height[0]=k=0;
continue;
}
if(k)k--;
j=sa[rank[i]-1];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
void solve(){
ll ans=1LL*n*(n+1)/2;
int i;
for(i=1;i<=n;i++)ans-=height[i];
printf("%lld\n",ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s);
n=strlen(s);
getsa();
getheight();
solve();
}
return 0;
}
D
题目描述
这题跟上一题重了…
解题思路
同上
AC代码
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
typedef long long ll;
char s[N];
int x[N],y[N],sa[N],c[10*N],rank[N],height[N],n;
void getsa(){
int i,k,m=10000;
n++;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=s[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;
for(k=1;k<=n;k<<=1){
int num=0;
for(i=n-k;i<n;i++)y[num++]=i;
for(i=0;i<n;i++)if(sa[i]>=k)y[num++]=sa[i]-k;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[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];
std::swap(x,y);
num=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]?num-1:num++;
if(num>=n)break;
m=num;
}
n--;
}
void getheight(){
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(!rank[i]){
height[0]=k=0;
continue;
}
if(k)k--;
j=sa[rank[i]-1];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
void solve(){
ll ans=1LL*n*(n+1)/2;
int i;
for(i=1;i<=n;i++)ans-=height[i];
printf("%lld\n",ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
scanf("%s",s);
n=strlen(s);
getsa();
getheight();
solve();
}
return 0;
}
E
题目描述
给定若干个长度 $≤ 1000000$ 的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：
ababab则最多有 $3$ 个ab连接而成。解题思路
枚举循环节，如果$l$是最小循环节长度，则有$s[0…n-l-1]==s[l…n-1]$。
思路1：后缀数组
如果$l$为最小循环节长度，则必有$rank[0]==rank[l]+1$且$height[rank[0]]==n-l$。
数据范围需要$DC3$，否则会$T$掉。
AC代码（2547ms）
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
typedef long long ll;
char str[N];
int s[N],sa[N*3],c[10*N],rank[N],height[N];
int wa[N],wb[N],ws[N],wv[N];
int c0(int *r,int a,int b){
return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b){
if(k==2)return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}
void sort(int *r,int *a,int *b,int n,int m){
int i;
for(i=0;i<n;i++)wv[i]=r[a[i]];
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[wv[i]]++;
for(i=1;i<m;i++)ws[i] += ws[i-1];
for(i=n-1;i>=0;i--)b[--ws[wv[i]]]=a[i];
}
void dc3(int *r,int *sa,int n,int m){
int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
r[n]=r[n+1]=0;
for(i=0;i<n;i++)if(i%3!=0)wa[tbc++]=i;
sort(r+2,wa,wb,tbc,m);
sort(r+1,wb,wa,tbc,m);
sort(r,wa,wb,tbc,m);
for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
if(p<tbc)dc3(rn,san,tbc,p);
else for(i=0;i<tbc;i++)san[rn[i]]=i;
for(i=0;i<tbc;i++)if(san[i]<tb)wb[ta++]=san[i]*3;
if(n%3==1)wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i<tbc;i++)wv[wb[i]=G(san[i])]=i;
for(i=0,j=0,p=0;i<ta&&j<tbc;p++)sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
for(;i<ta;p++)sa[p]=wa[i++];
for(;j<tbc;p++)sa[p]=wb[j++];
}
void getheight(int *s,int *sa,int n){
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(!rank[i]){
height[0]=k=0;
continue;
}
if(k)k--;
j=sa[rank[i]-1];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
int solve(int n){
int i;
for(i=1;i<=n;i++)
if(n%i==0&&rank[0]==rank[i]+1&&height[rank[0]]==n-i)return i;
return n;
}
int main(){
int i;
while(~scanf("%s",str)){
if(str[0]=='.'&&!str[1])break;
int n=strlen(str);
for(i=0;i<n;i++)s[i]=str[i]-'a'+1;
s[n]=0;
dc3(s,sa,n+1,105);
getheight(s,sa,n);
printf("%d\n",n/solve(n));
}
return 0;
}思路2：kmp
$next$数组保证了$s[0…n-l-1]==s[l…n-1]$性质，其中$l=n-next[n]$。
AC代码（125ms）
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char a[N];
int nxt[N],n;
int main(){
int i,j;
while(~scanf("%s",a)&&a[0]!='.'){
j=0;
n=strlen(a);
for(i=1;i<=n;i++){
while(j&&a[i]!=a[j])j=nxt[j];
if(a[i]==a[j])j++;
nxt[i+1]=j;
}
int l=n-nxt[n];
if(n%l==0)printf("%d\n",n/l);
else printf("1\n");
}
return 0;
}
F
题目描述
求一个串中连续重复出现次数最多的串的出现次数。
解题思路
枚举该串长度$i$，从头到尾以$i$为步长求出$LCP(suffix(k\times i),suffix((k+1)\times i))$，再向前延伸，每次更新答案为$max(ans,lcp/i+1)$。
复杂度为调和级数，$O(nlgn)$。
AC代码
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
int s[M],sa[M],rank[M],height[M];
int wa[M],wb[M],ws[M],wv[M];
int c0(int *r,int a,int b){
return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}
int c12(int k,int *r,int a,int b){
if(k==2)return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}
void sort(int *r,int *a,int *b,int n,int m){
int i;
for(i=0;i<n;i++)wv[i]=r[a[i]];
for(i=0;i<m;i++)ws[i]=0;
for(i=0;i<n;i++)ws[wv[i]]++;
for(i=1;i<m;i++)ws[i] += ws[i-1];
for(i=n-1;i>=0;i--)b[--ws[wv[i]]]=a[i];
}
void dc3(int *r,int *sa,int n,int m){
int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
r[n]=r[n+1]=0;
for(i=0;i<n;i++)if(i%3!=0)wa[tbc++]=i;
sort(r+2,wa,wb,tbc,m);
sort(r+1,wb,wa,tbc,m);
sort(r,wa,wb,tbc,m);
for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
if(p<tbc)dc3(rn,san,tbc,p);
else for(i=0;i<tbc;i++)san[rn[i]]=i;
for(i=0;i<tbc;i++)if(san[i]<tb)wb[ta++]=san[i]*3;
if(n%3==1)wb[ta++]=n-1;
sort(r,wb,wa,ta,m);
for(i=0;i<tbc;i++)wv[wb[i]=G(san[i])]=i;
for(i=0,j=0,p=0;i<ta&&j<tbc;p++)sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
for(;i<ta;p++)sa[p]=wa[i++];
for(;j<tbc;p++)sa[p]=wb[j++];
}
void getheight(int *s,int *sa,int n){
int i,j,k=0;
for(i=0;i<=n;i++)rank[sa[i]]=i;
for(i=0;i<n;i++){
if(!rank[i]){
height[0]=k=0;
continue;
}
if(k)k--;
j=sa[rank[i]-1];
while(s[i+k]==s[j+k])k++;
height[rank[i]]=k;
}
}
int st[20][N];
void init(int n){
int i,j;
for(i=0;i<=n;i++)st[0][i]=height[i];
for(i=n-1;i;i--)
for(j=1;(1<<j)+i-1<=n;j++)
st[j][i]=std::min(st[j-1][i],st[j-1][i+(1<<(j-1))]);
}
int query(int l,int r){
int m=0;
if(l>r)std::swap(l,r);
l++;
while((1<<(m+1))<r-l+1)m++;
return std::min(st[m][l],st[m][r-(1<<m)+1]);
}
int solve(int n){
int i,j,ans=1,lcp,remain;
for(i=1;i<=n;i++){
for(j=0;j+i<n;j+=i){
lcp=query(rank[j],rank[j+i]);
remain=i-lcp%i;
int start=j-remain;
if(start>=0&&lcp%i&&query(rank[start],rank[start+i])>=remain)
lcp+=remain;
ans=std::max(ans,lcp/i+1);
}
}
return ans;
}
int main(){
int i,n,t;
char a[10]={0};
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(i=0;i<n;i++)scanf("%s",a),s[i]=a[0]-'a'+1;
s[i]=0;
dc3(s,sa,n+1,4);
getheight(s,sa,n);
init(n);
printf("%d\n",solve(n));
}
return 0;
}
G
题目描述
解题思路
AC代码
2
H
题目描述
解题思路
AC代码
2
I
题目描述
解题思路
AC代码
2
J
题目描述
解题思路
AC代码
2
K
题目描述
解题思路
AC代码
2
L
题目描述
解题思路
AC代码
2
M
题目描述
解题思路
AC代码
2