大致题意:
给出一个长度小于100000的字符串,求字符串中字典序排在第k位的子串。
大致思路
联动ural1590 http://bbezxcy.iteye.com/blog/1457009
这里有一个后缀数组的基本规律,每个后缀去掉重复的前缀之后留下的就是所有的子串。
eg字符串 aabb 排列成后缀数组之后,|代表height计算出的和sa[i-1]相同的部分
sa[1]=0 aabb 子串有 aa aab aabb
sa[2]=1 a|bb 子串有 a ab abb
sa[3]=3 b 子串有 b
sa[4]=2 b|b 子串有 bb
先二分查找第k个子串大致在第几个sa(注意“大致”),然后向下扫描heigt值小于子串长度lth且sa值最小的子串
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int Max = 100004; int num[Max]; int sa[Max], rank[Max], height[Max]; int wa[Max], wb[Max], wv[Max], wd[Max]; int cmp(int *r, int a, int b, int l){ return r[a] == r[b] && r[a+l] == r[b+l]; } void da(int *r, int n, int m){ // 倍增算法 r为待匹配数组 n为总长度 m为字符范围 int i, j, p, *x = wa, *y = wb, *t; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[x[i]=r[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[x[i]]] = i; for(j = 1, p = 1; p < n; j *= 2, m = p){ for(p = 0, i = n-j; i < n; i ++) y[p ++] = i; for(i = 0; i < n; i ++) if(sa[i] >= j) y[p ++] = sa[i] - j; for(i = 0; i < n; i ++) wv[i] = x[y[i]]; for(i = 0; i < m; i ++) wd[i] = 0; for(i = 0; i < n; i ++) wd[wv[i]] ++; for(i = 1; i < m; i ++) wd[i] += wd[i-1]; for(i = n-1; i >= 0; i --) sa[-- wd[wv[i]]] = y[i]; for(t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++){ x[sa[i]] = cmp(y, sa[i-1], sa[i], j) ? p - 1: p ++; } } } void calHeight(int *r, int n){ // 求height数组。 int i, j, k = 0; for(i = 1; i <= n; i ++) rank[sa[i]] = i; for(i = 0; i < n; height[rank[i ++]] = k){ for(k ? k -- : 0, j = sa[rank[i]-1]; r[i+k] == r[j+k]; k ++); } } long long sub[Max]; int main(){ char str[Max]; int i, m=30, ans,len,n,h,lll,rrr; long long k,v; while(scanf("%s",str)!=EOF){ len=strlen(str); for(i=0;i<=len;i++)num[i]=str[i]-'a'+1; num[len]=0; da(num, len + 1, m); calHeight(num, len); scanf("%d",&n); sub[0]=0; height[len+1]=0; for(i=1;i<=len;i++){ sub[i]=(len-sa[i])-height[i]; sub[i]+=sub[i-1]; // cout<<sub[i]<<" sub"; }//cout<<endl; lll=rrr=0; while(n--){ scanf("%I64d",&v); k=(lll^rrr^v)+1; //k=v; if(k>sub[len]){ lll=0,rrr=0; printf("%d %d\n",lll,rrr); continue; } int low=1,high=len,mid,res=1; while(low<=high){ mid=(low+high)/2; if(sub[mid]>=k){ res=mid; high=mid-1; }else{ low=mid+1; } }//cout<<"res="<<res<<endl; lll=sa[res]; //rrr=len-(sub[res]-k+1); rrr=lll+height[res]+k-sub[res-1]-1; //rrr=lll+height[lll]+k-sub[res]+1; int lth=rrr-lll+1; // cout<<"init"<<lll<<" "<<rrr<<" "<<lth<<endl; while(res+1<=len&&height[res+1]>=lth){ res++; int tmpl=sa[res],tmpr=sa[res]+lth-1; lll=min(lll,tmpl); rrr=min(rrr,tmpr); }//rrr=lll+lth-1; lll++; rrr++; printf("%d %d\n",lll,rrr); } } return 0; }
相关推荐
杭电ACM课件2014版之(HDUACM2010版_13)二分匹配及其应用
HDU二分匹配及其应用,此PPT是刘春英老师版权所有, 特此贡献给广大编程爱好者,特别是对于ACMer
HDU图论题目分类
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu题目分类
HDUACM2010版13二分匹配及其应用.ppt
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
acm 技术大牛 课件 HDU 自学必备课件 全套齐全 (lecture_01)初识ACM (lecture_02)简单数学题 (lecture_03)递推求解 (lecture_04)动态规划...(lecture_12)二分匹配及其应用 (lecture_13)动态规划(2) 并查集
搜索 dfs 解题代码 hdu1241
其中有pku、hdu、zoj等各大oj的题目分类,pku的oj比较详细一点,按不同算法进行分类,均系从网上自行搜集的。
HDU的ACM,非常的好 涉及了很多算法,例如二分匹配、博弈、组合、最小生成树、搜索、动态规划、贪心算法
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。