后缀数组练习题若干
POJ 1743 不可重叠最长重复子串
二分答案。 即子串的长度，假设为k时。
利用height数组，将排序后的后缀分为若干组。
每组内的height值都不小于k。
然后只需查看组内是否有满足要求的两个不会产生重叠的子串即可。
#include <iostream>#include <cstdio>#include <cstring>#include <vector>#include <set>#include <queue>#include <cmath>#include <algorithm>#define MAXN 1111111#define MAXM 111#define INF 1000000000#define F(x) ((x)/3+((x)%3==1?0:tb))#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)using namespace std;int wa[MAXN] , wb[MAXN] , wv[MAXN] , tmp[MAXN];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); else 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++) tmp[i] = 0; for (i = 0; i < n; i++) tmp[wv[i]]++; for (i = 1; i < m; i++) tmp[i] += tmp[i-1]; for (i = n-1; i >= 0; i--) b[--tmp[wv[i]]] = a[i];}void dc3(int *r, int *sa, int n, int m){ int i, j, *rn = r + n; int *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 da(int str[], int sa[], int rank[], int height[], int n, int m){// for (int i = n; i < n * 3; i++)// str[i] = 0; dc3 (str , sa , n + 1 , m); int i, j, k; for (i = 0; i < n; i++){ sa[i] = sa[i + 1]; rank[sa[i]] = i; } for (i = 0, j = 0, k = 0; i < n; height[rank[i ++]] = k) if (rank[i] > 0) for (k ? k--: 0 , j = sa[rank[i]-1]; i + k < n && j + k < n && str[i + k] == str[j + k]; k++);}int lcp[MAXN];int r[MAXN];int sa[MAXN], rank[MAXN] , height[MAXN];int n;void getlcp(){ int k = rank[0]; lcp[k] = n; for(int i = k; i >= 2; i--) lcp[i - 1] = min(lcp[i], height[i]); for(int i = k + 1; i <= n; i++) lcp[i] = min(lcp[i - 1], height[i]);}char s[MAXN];bool ok(int k){ int rk = rank[k]; if(lcp[rk] == n - k) return true; return false;}int main(){ while(gets(s)) { if(s[0] == '.') break; n = strlen(s); for(int i = 0; i <= n; i++) r[i] = s[i]; da(r, sa, rank, height, n + 1, 130); getlcp(); int tmp = (int)sqrt(n + 0.5); int ans = 0; for(int i = 1; i <= tmp; i++) { if(n % i != 0) continue; if(ok(i)) ans = max(ans, n / i); if(ok(n / i)) ans = max(ans, i); } printf("%d\n", ans); } return 0;}