重温后缀数组（附6题）
初学后缀数组建议去hihocoder看看。
hihocoder 1403, 1407, 1415都是不错的题目。而且题目内附有详细解析。
代码如下：
# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 50010;
# define rank RANK
int sa[M], tsa[M], rank[M], cntA[M], cntB[M], A[M], B[M], height[M];
int n, k;
int ch[M];
inline void getSA() {
memset(cntA, 0, sizeof(cntA));
for (int i=1; i<=n; ++i) cntA[ch[i]]++;
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
}
for (int len = 1; rank[sa[n]] < n; len <<= 1) {
memset(cntA, 0, sizeof(cntA));
memset(cntB, 0, sizeof(cntB));
for (int i=1; i<=n; ++i) {
cntA[A[i] = rank[i]] ++;
cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
}
for (int i=1; i<=n; ++i) cntB[i] += cntB[i-1];
for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[A[tsa[i]]] -- ] = tsa[i];
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
}
}
for (int i=1, j=0; i<=n; ++i) {
if(j) --j;
while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
height[rank[i]] = j;
}
}
inline bool chk(int x) {
int cnt = 0;
for (int i=1; i<=n; ++i) {
if(height[i] < x) continue;
int j = i, cur = 2;
while(height[j+1] >= x && j+1 <= n)
++j, ++cur;
if(cur > cnt) cnt = cur;
i = j;
}
return cnt >= k;
}
int main() {
scanf("%d%d", &n, &k);
for (int i=1; i<=n; ++i) scanf("%d", &ch[i]);
getSA();
// puts("");
// for (int i=1; i<=n; ++i) printf("%d\n", height[i]);
int l = 0, r = n, mid, ans = 0;
while(1) {
if(r-l <= 3) {
for (int i=r; i>=l; --i)
if(chk(i)) {
ans = i;
break;
}
break;
}
mid = l+r >> 1;
if(chk(mid)) l = mid;
else r = mid;
}
printf("%d\n", ans);
return 0;
}
# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 100010;
# define rank RANK
int sa[M], tsa[M], rank[M], cntA[M], cntB[M], A[M], B[M], height[M];
int n;
int ch[M];
inline void getSA() {
memset(cntA, 0, sizeof(cntA));
for (int i=1; i<=n; ++i) cntA[ch[i]]++;
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
}
for (int len = 1; rank[sa[n]] < n; len <<= 1) {
memset(cntA, 0, sizeof(cntA));
memset(cntB, 0, sizeof(cntB));
for (int i=1; i<=n; ++i) {
cntA[A[i] = rank[i]] ++;
cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
}
for (int i=1; i<=n; ++i) cntB[i] += cntB[i-1];
for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[A[tsa[i]]] -- ] = tsa[i];
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
}
}
for (int i=1, j=0; i<=n; ++i) {
if(j) --j;
while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
height[rank[i]] = j;
}
}
inline bool chk(int x) {
int maxsa = 0, minsa = n;
for (int i=1; i<=n; ++i) {
if(height[i] < x) {
minsa = sa[i];
maxsa = sa[i];
} else {
minsa = min(minsa, sa[i]);
maxsa = max(maxsa, sa[i]);
if(maxsa - minsa >= x) return true;
}
}
return false;
}
int main() {
scanf("%d", &n);
for (int i=1; i<=n; ++i) scanf("%d", &ch[i]);
getSA();
// puts("");
// for (int i=1; i<=n; ++i) printf("%d\n", height[i]);
int l = 0, r = n, mid, ans = 0;
while(1) {
if(r-l <= 3) {
for (int i=r; i>=l; --i)
if(chk(i)) {
ans = i;
break;
}
break;
}
mid = l+r >> 1;
if(chk(mid)) l = mid;
else r = mid;
}
printf("%d\n", ans);
return 0;
}
# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 200010;
# define rank RANK
int sa[M], tsa[M], rank[M], cntA[M], cntB[M], A[M], B[M], height[M];
int n;
char ch[M];
inline void getSA() {
memset(cntA, 0, sizeof(cntA));
for (int i=1; i<=n; ++i) cntA[ch[i]]++;
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
}
for (int len = 1; rank[sa[n]] < n; len <<= 1) {
memset(cntA, 0, sizeof(cntA));
memset(cntB, 0, sizeof(cntB));
for (int i=1; i<=n; ++i) {
cntA[A[i] = rank[i]] ++;
cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
}
for (int i=1; i<=n; ++i) cntB[i] += cntB[i-1];
for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[A[tsa[i]]] -- ] = tsa[i];
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
}
}
for (int i=1, j=0; i<=n; ++i) {
if(j) --j;
while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
height[rank[i]] = j;
}
}
int main() {
scanf("%s", ch+1);
int curl = strlen(ch+1);
ch[++curl] = '$';
scanf("%s", ch + curl + 1);
n = strlen(ch+1);
getSA();
// puts("");
// for (int i=1; i<=n; ++i) printf("%d\n", height[i]);
int ans = 0;
for (int i=2; i<=n; ++i) {
int cur = sa[i], pre = sa[i-1];
int big, sma; big = max(cur, pre); sma = min(cur, pre);
if(big > curl && sma <= curl)
ans = max(ans, height[i]);
}
printf("%d\n", ans);
return 0;
}
BZOJ做题：
BZOJ1031
【题解】裸后缀数组。
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;
# define rank RANK
int sa[M], tsa[M], rank[M], A[M], B[M], cntA[M], cntB[M], n;
char ch[M];
const int N = 256;
inline void getsa() {
memset(cntA, 0, sizeof(cntA));
for (int i=1; i<=n; ++i) cntA[ch[i]] ++;
for (int i=1; i<=N; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
}
for (int len=1; rank[sa[n]] < n; len <<= 1) {
memset(cntA, 0, sizeof(cntA));
memset(cntB, 0, sizeof(cntB));
for (int i=1; i<=n; ++i) {
cntA[A[i] = rank[i]] ++;
cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
}
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];
for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i];
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
}
}
}
int main() {
scanf("%s", ch+1);
n = strlen(ch+1);
for (int i=1; i<=n; ++i) ch[i+n] = ch[i];
n <<= 1;
getsa();
for (int i=1; i<=n; ++i) {
if(sa[i] <= (n>>1))
printf("%c", ch[sa[i]+(n>>1)-1]);
}
return 0;
}
BZOJ4278
后缀数组比较大小+贪心选取。
# include <stdio.h>
# include <string.h>
# include <algorithm>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 500010;
# define rank RANK
int sa[M], tsa[M], rank[M], A[M], B[M], cntA[M], cntB[M], n;
int ch[M];
const int N = 1010;
inline void getsa() {
memset(cntA, 0, sizeof(cntA));
for (int i=1; i<=n; ++i) cntA[ch[i]] ++;
for (int i=1; i<=N; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
}
for (int len=1; rank[sa[n]] < n; len <<= 1) {
memset(cntA, 0, sizeof(cntA));
memset(cntB, 0, sizeof(cntB));
for (int i=1; i<=n; ++i) {
cntA[A[i] = rank[i]] ++;
cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
}
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];
for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i];
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
}
}
}
int n1, n2;
int a[M], b[M];
int main() {
n = 0;
scanf("%d", &n1);
for (int i=1; i<=n1; ++i) {
scanf("%d", &a[i]);
ch[++n] = a[i];
}
scanf("%d", &n2);
ch[++n] = 1001;
for (int i=1; i<=n2; ++i) {
scanf("%d", &b[i]);
ch[++n] = b[i];
}
getsa();
int pa = 1, pb = 1;
while(pa <= n1 && pb <= n2) {
int sA = rank[pa], sB = rank[n1 + pb + 1];
if(sA < sB) {
printf("%d ", a[pa]);
++pa;
} else {
printf("%d ", b[pb]);
++pb;
}
}
while(pa <= n1) {
printf("%d ", a[pa]);
++pa;
}
while(pb <= n2) {
printf("%d ", b[pb]);
++pb;
}
return 0;
}
BZOJ3172
后缀数组求完后乱搞即可（暴力） 实际上正解应该是AC自动机。
# include <stdio.h>
# include <algorithm>
# include <string.h>
// # include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 1600010;
# define rank RANK
int n, sa[M], tsa[M], cntA[M], cntB[M], rank[M], A[M], B[M];
char ch[M];
int height[M];
const int N = 256;
int t, beg[M], lens[M];
inline void getsa() {
memset(cntA, 0, sizeof(cntA));
for (int i=1; i<=n; ++i) cntA[ch[i]] ++;
for (int i=1; i<=N; ++i) cntA[i] += cntA[i-1];
for (int i=n; i; --i) sa[cntA[ch[i]] --] = i;
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(ch[sa[i]] != ch[sa[i-1]]) ++rank[sa[i]];
}
for (int len=1; rank[sa[n]] < n; len <<= 1) {
memset(cntA, 0, sizeof(cntA));
memset(cntB, 0, sizeof(cntB));
for (int i=1; i<=n; ++i) {
cntA[A[i] = rank[i]] ++;
cntB[B[i] = ((i+len <= n) ? rank[i+len] : 0)] ++;
}
for (int i=1; i<=n; ++i) cntA[i] += cntA[i-1], cntB[i] += cntB[i-1];
for (int i=n; i; --i) tsa[cntB[B[i]] --] = i;
for (int i=n; i; --i) sa[cntA[A[tsa[i]]] --] = tsa[i];
rank[sa[1]] = 1;
for (int i=2; i<=n; ++i) {
rank[sa[i]] = rank[sa[i-1]];
if(A[sa[i]] != A[sa[i-1]] || B[sa[i]] != B[sa[i-1]]) ++rank[sa[i]];
}
}
for (int i=1, j=0; i<=n; ++i) {
if(j) j--;
while(ch[i+j] == ch[sa[rank[i]-1] + j]) ++j;
height[rank[i]] = j;
}
}
int main() {
scanf("%d", &t);
int cur = 1;
for (int i=1; i<=t; ++i) {
beg[i] = cur;
scanf("%s", ch+cur);
cur = strlen(ch+1);
lens[i] = cur - beg[i] + 1;
ch[++cur] = '$';
++cur;
}
--cur;
n = cur;
getsa();
for (int i=1; i<=t; ++i) {
int cur = rank[beg[i]];
int l, r;
l=r=cur;
while(height[l] >= lens[i] && l>0) --l;
while(height[r+1] >= lens[i] && r<n) ++r;
printf("%d\n", r-l+1);
}
return 0;
}
2022年9月08日 18:51
Chhattisgarh State Department of School Education (Elementary Level Primary Education) and other private school teaching staff of the state have designed and suggested CG Board 4th Class Model Paper 2023 with sample answers along with Mock Test and Practice Questions for Term1 & Term 2 Exams of the Course to All Languages and Subjects. CG Board Model Paper Class 4 Every 4th Standard Student of SCERT & NCERT Syllabus Studying in Government or Private schools of Hindi Medium, English Medium and Urdu Medium can download and practice the CGBSE STD-4 Question Paper 2023 Pdf for Part-A, Part-B, Part-C and Part-D exam.