首页 > 代码库 > POJ 3882 Stammering Aliens 后缀数组height应用
POJ 3882 Stammering Aliens 后缀数组height应用
题目来源:POJ 3882 Stammering Aliens
题意:给你m一个一个字符串 求至少出现m次的最长字符串 可以在字符串中重叠出现
思路:二分长度l 然后从height数组中找长度大于等于l的前缀
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 40010; char s[maxn]; int sa[maxn]; int t[maxn], t2[maxn], c[maxn]; int rank[maxn], height[maxn]; int pos, lim; void build_sa(int m, int n) { int i, *x = t, *y = t2; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[i] = s[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(int k = 1; k <= n; k <<= 1) { int p = 0; for(i = n-k; i < n; i++) y[p++] = i; for(i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i] - k; for(i = 0; i < m; i++) c[i] = 0; for(i = 0; i < n; i++) c[x[y[i]]]++; for(i = 0; i < m; i++) c[i]+= c[i-1]; for(i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; swap(x,y); p = 1; x[sa[0]] = 0; for(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; } } void getHeight(int n) { int k = 0; for(int i = 0; i <= n; i++) rank[sa[i]] = i; for(int i = 0; i < n; i++) { if(k) k--; int j = sa[rank[i]-1]; while(s[i+k] == s[j+k]) k++; height[rank[i]] = k; } } bool ok(int l, int n) { int flag = 0; int cnt = 1; pos = 0; int p = -1; for(int i = 1; i <= n; i++) { if(height[i] >= l) { cnt++; p = max(p, sa[i]); } else { p = sa[i]; cnt = 1; } if(cnt >= lim) { flag = 1; pos = max(pos, p); } } if(flag) return true; return false; } int main() { int l, r, n; while(scanf("%d", &lim) && lim) { scanf("%s", s); n = strlen(s); if(lim == 1) { printf("%d 0\n", n); continue; } l = 1; r = n; int ans = -1; int ans2; build_sa(256, n+1); getHeight(n); while(l <= r) { int m = (l + r) >> 1; if(ok(m, n)) { ans = m; ans2 = pos; l = m+1; } else r = m-1; } if(ans == -1) puts("none"); else { printf("%d %d\n", ans, ans2); } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。