首页 > 代码库 > HDU 4691
HDU 4691
卡了两天的题，今天终于想明白到底是哪里出了问题了。原来只是因为 j+(1<<i)-1<=n 我理解成了 j+(1<<i)<n。乍看之下还真以为这是对的呢，问了好多人都被骗了。
说说题吧。题目的描述很清晰，一道后缀数组的题，我第一次写后缀数组，也是看了好多资料，以及题解才勉强写出来，可是就是因为刚刚那个大坑，浪费了两天的时间。也不能说是浪费吧，至少每一次找错，都是在加深我对算法和代码的理解。
后缀数组最重要的是对后缀子序列的排序，求出h[]，之后再写一个rmq就可以O(1)时间求出两个后缀的LCP。
下面的是代码。
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int maxn = 100010;#define max(a,b) (a > b ? a : b)#define min(a,b) (a < b ? a : b)char c[maxn];int h[maxn], rank[maxn], sa[maxn], t1[maxn], t2[maxn], z[maxn];int ll[maxn], rmq[40][maxn], rmq2[maxn][40];bool cmp(int tmp[], int a, int b, int t){ return tmp[a] == tmp[b] && tmp[a+t] == tmp[b+t];}void suffix(int len, int sum){ int *x = t1; int *y = t2; len++; for(int i = 0; i < sum; i++) z[i] = 0; for(int i = 0; i < len; i++) z[x[i] = c[i]]++; for(int i = 1; i < sum; i++) z[i] += z[i-1]; for(int i = len -1; i >= 0; i--) sa[--z[x[i]]] = i; for(int j = 1; j <= len; j <<= 1) { int p = 0; for(int i = len - j; i < len; i++) y[p++] = i; for(int i = 0; i < len; i++) if(sa[i] >= j) y[p++] = sa[i] - j; for(int i = 0; i < sum; i++) z[i] = 0; for(int i = 0; i < len; i++) z[x[y[i]]]++; for(int i = 1; i < sum; i++) z[i] += z[i - 1]; for(int i = len - 1; i >= 0; i--) sa[--z[x[y[i]]]] = y[i]; swap(x,y); p = 1; x[sa[0]] = 0; for(int i = 1; i < len; i++) x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p-1: p++; if(p >= len) break; sum = p; } int k = 0; len--; for(int i = 0; i <= len; i++) rank[sa[i]] = i; for(int i = 0; i < len; i++) { int j = sa[rank[i] - 1]; while(c[i + k] == c[j + k]) k++; h[rank[i]] = k; if(k) k--; }}void init(){ ll[0]= -1; for(int i = 1; i < maxn; i++) if((i & (i - 1)) == 0) ll[i] = ll[i - 1] + 1; else ll[i] = ll[i - 1];}/*void init_rmq(int n){ for(int i=1;i<=n;i++)rmq[0][i]=h[i]; for(int i=1;i<=ll[n];i++) for(int j=1;j+(1<<i)-1<=n;j++) { int a=rmq[i-1][j]; int b=rmq[i-1][j+(1<<(i-1))]; if(a<b)rmq[i][j]=a; else rmq[i][j]=b; }}*/void init_rmq(int n){ for(int i = 1; i <= n; i++) rmq[0][i] = h[i]; int i, j; for(i=1; i<=ll[n];i++) { for(j=1;(1<<i)+j-1<=n ;j++) { if(rmq[i-1][j] < rmq[i-1][j+(1<<(i-1))]) rmq[i][j] = rmq[i-1][j] ; else rmq[i][j] = rmq[i-1][j+(1<<(i - 1))]; } }}int qury_rmq(int ql, int qr){ int t =ll[qr - ql + 1]; qr -= (1 << t) - 1; return min(rmq[t][ql], rmq[t][qr]);}int cal(int t){ if(t == 0) return 1; int ret = 0; while(t) { ret++; t /= 10; } return ret;}int main(){ freopen("in.txt","r",stdin); freopen("out(2).txt","w",stdout); init(); while(scanf("%s", c) == 1) { int len = strlen(c); c[len] = 0; suffix(len, 128); init_rmq(len); long long ans1 = 0, ans2 = 0; int q; cin >> q; int prel, prer; cin >> prel >> prer; ans1 += (prer - prel + 1); ans2 += (prer - prel + 3); q--; int same = 0; while(q--) { int l, r; scanf("%d%d", &l, &r); if(l == prel) same = maxn * 100; else same = qury_rmq(min(rank[l], rank[prel]) + 1, max(rank[l], rank[prel])); //cout << same << endl; same = min(prer - prel, same); same = min(r - l, same); ans1 += r - l + 1; ans2 += r - l - same + 2 + cal(same); //cout << same << " " << l << " " << r << endl; prel = l; prer = r; } printf("%I64d %I64d\n", ans1, ans2); }}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。