本文共 3099 字，大约阅读时间需要 10 分钟。
后缀数组的应用。和男人八题那个后缀数组差不多。
1 /* 2890 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 #include 22 using namespace std; 23 //#pragma comment(linker,"/STACK:102400000,1024000") 24 25 #define sti set 26 #define stpii set > 27 #define mpii map 28 #define vi vector 29 #define pii pair 30 #define vpii vector > 31 #define rep(i, a, n) for (int i=a;i =a;--i) 33 #define clr clear 34 #define pb push_back 35 #define mp make_pair 36 #define fir first 37 #define sec second 38 #define all(x) (x).begin(),(x).end() 39 #define SZ(x) ((int)(x).size()) 40 #define lson l, mid, rt<<1 41 #define rson mid+1, r, rt<<1|1 42 43 const int maxn = 50050; 44 int a[maxn], b[maxn], aa[maxn]; 45 int pos[maxn], pn; 46 int rrank[maxn], height[maxn], sa[maxn]; 47 int wa[maxn], wb[maxn], wc[maxn], wv[maxn]; 48 int n, k, at; 49 50 bool cmp(int *r, int a, int b, int l) { 51 return r[a]==r[b] && r[a+l]==r[b+l]; 52 } 53 54 void da(int *r, int *sa, int n, int m) { 55 int i, j, *x=wa, *y=wb, *t, p; 56 57 for (i=0; i =0; --i) sa[--wc[x[i]]] = i; 61 for (j=1,p=1; p = j) y[p++] = sa[i] - j; 64 for (i=0; i =0; --i) sa[--wc[wv[i]]] = y[i]; 69 for (t=x, x=y, y=t, i=1,p=1,x[sa[0]]=0; i = bound) { 93 p = pos[j]; 94 ++kk; 95 } 96 } 97 98 if (kk >= k) 99 return true;100 pn = 0;101 pos[pn++] = sa[i++];102 } else {103 pos[pn++] = sa[i++];104 }105 }106 at = sa[n-1];107 sort(pos, pos+pn);108 int kk = 1, p = pos[0];109 rep(j, 1, pn) {110 if (pos[j]-p >= bound) {111 p = pos[j];112 ++kk;113 }114 }115 116 if (kk >= k)117 return true;118 119 return false;120 }121 122 void printSa(int n) {123 for (int i=1; i<=n; ++i)124 printf("%d ", sa[i]);125 putchar('\n');126 }127 128 void printHeight(int n) {129 for (int i=1; i<=n; ++i)130 printf("%d ", height[i]);131 putchar('\n');132 }133 134 void solve() {135 sort(b, b+n);136 int nn = unique(b, b+n) - b;137 138 rep(i, 0, n)139 aa[i] = lower_bound(b, b+nn, a[i]) - b + 1;140 aa[n] = 0;141 142 da(aa, sa, n+1, nn+4);143 calheight(aa, sa, n);144 145 #ifndef ONLINE_JUDGE146 // printSa(n);147 // printHeight(n);148 #endif149 150 int l = 1, r = n, mid;151 int ans = 0, fr;152 153 while (l <= r) {154 mid = (l + r) >> 1;155 if (judge(mid)) {156 ans = mid;157 fr = at;158 l = mid + 1;159 } else {160 r = mid - 1;161 }162 }163 164 printf("%d\n", ans);165 rep(i, 0, ans)166 printf("%d\n", b[aa[fr+i]-1]);167 }168 169 int main() {170 ios::sync_with_stdio(false);171 #ifndef ONLINE_JUDGE172 freopen("data.in", "r", stdin);173 freopen("data.out", "w", stdout);174 #endif175 176 int t;177 178 scanf("%d", &t);179 while (t--) {180 scanf("%d %d", &n, &k);181 rep(i, 0, n) {182 scanf("%d", &a[i]);183 b[i] = a[i];184 }185 solve();186 if (t)187 putchar('\n');188 }189 190 #ifndef ONLINE_JUDGE191 printf("time = %d.\n", (int)clock());192 #endif193 194 return 0;195 }
转载于:https://www.cnblogs.com/bombe1013/p/5178848.html