首页 > 代码库 > HDU 5008 Boring String Problem
HDU 5008 Boring String Problem
题意：给定一个串长度<=1e5，将其所有的不同的字串按照字典序排序，然后q个询问，每次询问字典序第k小的的起始坐标，并且起始坐标尽量小。
分析：
一开始看错题意，没有意识到是求不同的字串中第k小的，果断不知道怎么做，感觉如果题目改成这样，似乎还有点难度，至少对我来说。
好了，这个题目是考虑不同的字串，首先后缀数组处理，也就是讲后缀按照字典序排序，对于每个后缀开始的字串，如h[i]，容易知道i和i-1的后缀的LCP长度为h[i]那么i中除开前h[i]个字串，之后的字串在i-1之前都是没有出现过的，而且字典序要比之前的大，这样的字串数目时len-sa[i]-h[i]，那么对于每个i用val[i]表示，sum[i]表示前i项的val值之和，对于第k小的字串，找到一个sum[i]>k,然后判断一下sum[i-1]是不是==k，不是的话说明第k小的字串一定在后缀i的字串中出现过，并算出长度L。然后再确定其在整个字符串中出现的最左位置，L>h[i]显然成立，所以L只能在i之后的后缀的字串中出现，找到一个范围i~r，使得之间的h值>=L,然后RMQ求出最小的sa值，也就是字串出现的最左位置。
话说暴力查找最左位置，竟然也能水过，而且速度还有快，测试数据里面肯定没有10000个a，每次询问第1小的字串这组数据。
考虑相同的字串，询问第k小的怎么做？
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <vector> 4 #include <algorithm> 5 #define inf 0x0f0f0f0f 6 #define pb push_back 7 #define bug(x) printf("line %d: >>>>>>>>>>>>>>>\n", (x)); 8 #define in freopen("F:\\code\\data\\data.txt", "r", stdin); 9 #define out freopen("F:\\code\\data\\data_out.txt", "w", stdout); 10 11 #define SZ(x) ((int)x.size()) 12 #define lson rt<<1, l, m 13 #define rson rt<<1|1, m+1, r 14 #define fi first 15 #define se second 16 using namespace std; 17 typedef long long LL; 18 const int maxn = (int)1e5 + 100; 19 int s[maxn], sa[maxn], t[maxn], t2[maxn], rk[maxn], h[maxn], c[maxn]; 20 int n, m; 21 LL lans, rans; 22 LL sum[maxn], val[maxn]; 23 24 void buildSa(int m) 25 { 26 int *x = t, *y = t2; 27 for(int i = 0; i < m; i++) c[i] = 0; 28 for(int i = 0; i < n; i++) c[x[i]=s[i]]++; 29 30 for(int i = 1; i < m; i++) c[i] += c[i-1]; 31 for(int i = n-1; i >= 0; i--) sa[--c[x[i]]] = i; 32 33 for(int k = 1; k <= n; k <<= 1) 34 { 35 int p = 0; 36 for(int i = n-k; i < n; i++) y[p++] = i; 37 for(int i = 0; i < n; i++) if(sa[i] >= k) y[p++] = sa[i]-k; 38 39 for(int i = 0; i < m; i++) c[i] = 0; 40 for(int i = 0; i < n; i++) c[x[i]]++;// 41 for(int i = 1; i < m; i++) c[i] += c[i-1]; 42 for(int i = n-1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i]; 43 44 p = 1; 45 swap(x, y); 46 x[sa[0]] = 0; 47 48 for(int i = 1; i < n; i++) 49 x[sa[i]] = y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k] ? p-1 : p++; 50 m = p; 51 if(p >= n) 52 break; 53 } 54 } 55 void getHeight() 56 { 57 int k = 0, j; 58 h[0] = 0; 59 for(int i = 0; i < n; i++) rk[sa[i]] = i; 60 for(int i = 0; i < n; i++) 61 { 62 if(k) k--; 63 if(rk[i] == 0) 64 continue; 65 j = sa[rk[i]-1]; 66 while(s[i+k] == s[j+k]) 67 k++; 68 h[rk[i]] = k; 69 } 70 } 71 int dp[maxn][20], mx[maxn][20]; 72 void rmqInit(int a[][20], int h[]) 73 { 74 for(int i = 0; i < n; i++) a[i][0] = i; 75 for(int k = 1; (1<<k) <= n; k++) 76 for(int i = 0; i + (1<<k) <= n; i++) 77 a[i][k] = h[a[i][k-1]] < h[a[i+(1<<(k-1))][k-1]] ? a[i][k-1] : a[i+(1<<(k-1))][k-1]; 78 } 79 int RMQ(int l, int r, int a[][20], int h[]) 80 { 81 if(l > r) swap(l, r); 82 int k = 0; 83 while((1<<(k+1)) < r-l+1) k++; 84 return h[a[l][k]] < h[a[r-(1<<k)+1][k]] ? a[l][k] : a[r-(1<<k)+1][k]; 85 } 86 char str[maxn]; 87 int check(int l, int r) 88 { 89 return h[RMQ(l, r, dp, h)]; 90 } 91 void solve(LL k) 92 { 93 if(k > sum[n-1]) 94 { 95 lans = rans = 0; 96 return; 97 } 98 int kk = upper_bound(sum+1, sum+n, k)-sum; 99 if(sum[kk-1] == k)100 kk--;101 k -= sum[kk-1];102 103 int len = h[kk]+k;104 int x = sa[kk];105 if(kk+1 < n && h[kk+1] >= len)106 {107 int l = kk+1, r = n;108 while(r-l > 1)109 {110 int mid = (l+r)>>1;111 if(check(mid, kk+1) >= len)112 l = mid;113 else r = mid;114 }115 x = min(x, sa[RMQ(kk+1, l, mx, sa)]);116 }117 lans = x+1, rans = x+len;118 }119 int main()120 {121 122 123 while(scanf("%s", str) == 1)124 {125 n = 0;126 for(int i = 0; str[i]; i++)127 s[n++] = str[i]-‘a‘+1;128 s[n++] = 0;129 buildSa(30);130 getHeight();131 rmqInit(dp, h);132 rmqInit(mx, sa);133 // bug(1)134 int q;135 lans = rans = 0;136 for(int i = 1; i < n; i++)137 {138 val[i] = n-1-sa[i]-h[i];139 sum[i] = sum[i-1] + val[i];140 }141 for(int t = scanf("%d", &q); t <= q; t++)142 {143 LL v;144 scanf("%I64d", &v);145 LL k = (lans^rans^v)+1;146 solve(k);147 printf("%I64d %I64d\n", lans, rans);148 }149 }150 return 0;151 }
HDU 5008 Boring String Problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。