HDU 2459 PKU 3693 Maximum repetition substring 后綴數組 RMQ

2019-11-14 11:43:42

字體：大中小

來源：轉載

供稿：網友

題目地址：

HDU 2459 PKU 3696

題意：

給一個長度不超過1e5 $1e5$ 的字符串，找出其中一個子串，要求該子串能夠被分割成盡可能多的相同的字符串，若有多個符合要求的子串，輸出字典序最小的那個。

思路：

圖片不看也沒關系，但這個是羅穗騫大佬在他的論文《后綴數組——處理字符串的有力工具》里的原話，然后這是他的spoj687的代碼：http://paste.Ubuntu.com/23923746/，本人就是參考他的代碼，明白了思路的論文第19頁

RMQ部分只是用來求lcp的，不說了枚舉子串重復部分的長度L，然后以L為步長，枚舉題目所給的字符串下標，設lcp是suffix[L]和suffix[2 * L]的公共前綴，只要lcp>=L $lcp>=L$ ，重復的字符串就出現了（首先兩者相同的部分超過了suffix[L]和suffix[2 * L]的距離，然后suffix[2 * L]作為suffix[L] 的子串，重復lcp部分，就構成了一個有重復的字符串，可能這里有點繞……不懂的讀者可以自己舉例理解下）。重復部分的重復次數自然就是lcp/L+1 $lcp / L + 1$ （兩字符串公共部分的長度 / 重復部分的長度 + suffix[L]到suffix[2 * L]之間的子串個數）然后考慮一個特殊情況，比如說如下字符： 0123123123 就是按上述方法計算的話，算出來的字符是312312，原因是因為枚舉時出了問題（畢竟不是一個個枚舉的，而是有步長的枚舉），考慮suffix[3]與suffix[L]的lcp長度為4，比枚舉的長度3多了一個1，可以往前再走L?lcp $L - lcp % L = 2$ 步（1+2==3 $1 + 2 == 3$ ），看看這個后綴與其后面L的后綴的lcp長度是否大于等于L?lcp $L - lcp % L$ ，如果比前面走的步數要大的話，說明少計算了一次重復部分。輸出答案的部分參考了cxlove的，本來自己是特判加枚舉子串時直接判定答案的，可以不知道哪里寫丑了，總是有問題，后面就換成了cxlove的思路QAQ，他的題解：http://blog.csdn.net/acm_cxlove/article/details/7941205

可能說的不好，還請讀者多多思考

代碼：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int MAXN = 1e5 + 5;char str[MAXN];int sa[MAXN], Rank[MAXN], height[MAXN], wv[MAXN], c[MAXN];int d[MAXN][20];int cnt, stk[MAXN];bool cmp(int *r, int a, int b, int l) { return r[a] == r[b] && r[a + l] == r[b + l];}void da(char *r, int n, int m) { int i, j, p, *x = Rank, *y = height; for (i = 0; i < m; ++i) c[i] = 0; for (i = 0; i < n; ++i) ++c[x[i] = r[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 (j = 1, p = 1; p < n; j *= 2, m = p) { for (p = 0, i = n - j; i < n; ++i) y[p++] = i; for (i = 0; i < n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j; for (i = 0; i < n; ++i) wv[i] = x[y[i]]; for (i = 0; i < m; ++i) c[i] = 0; for (i = 0; i < n; ++i) ++c[wv[i]]; for (i = 1; i < m; ++i) c[i] += c[i - 1]; for (i = n - 1; i >= 0; --i) sa[--c[wv[i]]] = y[i]; for (swap(x, y), p = 1, x[sa[0]] = 0, i = 1; i < n; ++i) x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++; }}void calheight(char *r, int n) { int i, j, k = 0; for (i = 1; i <= n; ++i) Rank[sa[i]] = i; for (i = 0; i < n; height[Rank[i++]] = k) for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; ++k);}void RMQ_init(int *a, int n) { for (int i = 0; i < n; ++i) d[i][0] = a[i]; for (int j = 1; (1 << j) <= n; ++j) for (int i = 0; i + (1 << j) - 1 < n; ++i) d[i][j] = min(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);}int RMQ(int L, int R) { L = Rank[L], R = Rank[R]; if (L > R) swap(L, R); ++L; int k = 0; while ((1 << (k + 1)) <= R - L + 1) ++k; return min(d[L][k], d[R - (1 << k) + 1][k]);}int main() { //freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); int kase = 0; while (~scanf("%s", str)) { if (str[0] == '#') break; int len = strlen(str), maxr = 0, k, jj, now; da(str, len + 1, 'z' + 1); calheight(str, len); RMQ_init(height, len + 1); for (int i = 1; i < len; ++i) { for (int j = 0; j + i < len; j += i) { k = RMQ(j, j + i); now = k / i + 1; jj = j - (i - k % i); if (jj >= 0 && RMQ(jj, jj + i) >= (i - k % i)) ++now; if (now > maxr) { cnt = 0; maxr = now; stk[cnt++] = i; } else if (now == maxr) { stk[cnt++] = i; } } } for (int i = 1; i <= len; ++i) { for (int j = 0; j < cnt; ++j) { if (RMQ(sa[i], sa[i] + stk[j]) >= (maxr - 1) * stk[j]){ jj = sa[i]; k = stk[j]; goto END; } } } END: