UVALive - 4513 Stammering Aliens——后缀数组

UVALive - 4513 Stammering Aliens——后缀数组

UVALIVE崩了两周，都忘了这道题是什么了233...

#include using namespace std;const int maxn = 1e5;char s[maxn];int sa[maxn], t[maxn], t2[maxn], c[maxn], n, m;void build_sa(int m) { int i, *x = t, *y = t2; for (int i = 0; i < m; i++) c[i] = 0; for (int i = 0; i < n; i++) c[x[i] = s[i]]++; for (int i = 1; i < m; i++) c[i] += c[i-1]; for (int i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i; for (int k = 1; k <= n; k <<= 1) { int p = 0; for (int i = n - k; i < n; i++) y[p++] = i; for (int i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i]-k; for (int i = 0; i < m; i++) c[i] = 0; for (int i = 0; i < n; i++) c[x[y[i]]]++; for (int i = 0; i < m; i++) c[i] += c[i-1]; for (int i = n-1; i >= 0; i--)sa[--c[x[y[i]]]] = y[i]; swap(x, y); p = 1; x[sa[0]] = 0; for (int i = 1; i < n; i++) x[sa[i]] = y[sa[i-1]]== y[sa[i]] && y[sa[i-1]+k]== y[sa[i]+k] ? p-1 : p++; if (p >= n) break; m = p; }}int ran[maxn], height[maxn];void getHeight() { int i, j, k = 0; for (i = 0; i < n; i++) ran[sa[i]] = i; for (i = 0; i < n; i++) { if (k) k--; int j = sa[ran[i]-1]; while (i+k < n && j+k < n && s[i+k] == s[j+k]) k++; height[ran[i]] = k; }}vector block[maxn];void output(int p) { for (int i = 0; i < n; i++) block[i].clear(); int cnt = 0; block[cnt].push_back(sa[0]); for (int i = 1; i < n; i++) { if (height[i] < p) cnt++; block[cnt].push_back(sa[i]); } int ans = 0; for (int i = 0; i <= cnt; i++) { if (block[i].size() >= m) { for (int j = 0; j < block[i].size(); j++) ans = max(ans, block[i][j]); } } printf("%d %d\n", p, ans);}bool judge(int p) { int cnt = 1; for (int i = 1; i < n; i++) { if (height[i] < p) cnt = 1; else cnt++; if (cnt >= m) return true; } return false;}void solve() { bool ok = false; int l = 1, r = n; while (l <= r) { int mid = (l + r)>>1; if (judge(mid)) { l = mid + 1; ok = true; } else r = mid - 1; } if (!ok) puts("none"); else output(r);}int main() { while (~scanf("%d", &m) && m) { scanf("%s", s); n = strlen(s); if (m == 1) { printf("%d 0\n", n); continue; } s[n++] = '#'; build_sa(128); getHeight(); solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。