- 浏览: 378784 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出两个字符串s1,s2。现在我们可以把s1接到s2后面或者把s2接到s1后面,拼接的方式是:如果前面字符的后缀中和后面字符串的前缀中存在相同的部分,我们便把这一部分从第一个字符串中去掉,并把后面的字符串接上去。现在求拼接后长度最小并且字典序最小的字符串。
大致思路:
把两个字符串拼在一起,中间插入分隔符。对这个串求出后缀数组,并根据后缀数组求出s1+s2生成的字符串和s2+s1生成的字符串。比较这两个串,输出长度最小或者长度相同字典序最小的那个。
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int nMax =1000000; int num[nMax]; int sa[nMax], rank[nMax], height[nMax]; int wa[nMax], wb[nMax], wv[nMax], wd[nMax]; 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 ++); } } int Log[nMax]; int best[20][nMax]; void initRMQ(int n) {//初始化RMQ for(int i = 1; i <= n ; i ++) best[0][i] = height[i]; for(int i = 1; i <= Log[n] ; i ++) { int limit = n - (1<<i) + 1; for(int j = 1; j <= limit ; j ++) { best[i][j] = min(best[i-1][j] , best[i-1][j+(1<<i>>1)]); } } } int lcp(int a,int b) {//询问a,b后缀的最长公共前缀 a = rank[a]; b = rank[b]; if(a > b) swap(a,b); a ++; int t = Log[b - a + 1]; return min(best[t][a] , best[t][b - (1<<t) + 1]); } int len1,len2,n; char str[nMax],str1[nMax],str2[nMax]; void solve(){ int i,j,a,b,ans1=len1,ans2=len2,k1,k2; for(i=len1-1;i>=0;i--){ a=lcp(i,len1+1); b=len1-i; if(a>=b){ ans1=i; } } k1=0; for(i=0;i<ans1;i++){ str1[k1++]=num[i]+'a'-1; } for(i=0;i<len2;i++){ str1[k1++]=str[i]; }str1[k1]='\0'; for(i=len2-1;i>=0;i--){ a=lcp(i+len1+1,0); b=len2-i; if(a>=b){ ans2=i; } } k2=0; for(i=0;i<ans2;i++){ str2[k2++]=num[i+len1+1]+'a'-1; } for(i=0;i<len1;i++){ str2[k2++]=num[i]+'a'-1;; }str2[k2]='\0'; if(k1>k2){ printf("%s\n",str2); return; } if(k1<k2){ printf("%s\n",str1); return; } if(strcmp(str1,str2)<0){ printf("%s\n",str1); } else{ printf("%s\n",str2); } } int main(){ int i,j,a,b,c,loc; Log[0] = -1; for(int i=1;i<=nMax;i++){ Log[i]=(i&(i-1))?Log[i-1]:Log[i-1] + 1 ; } while(scanf("%s",str)!=EOF){ n=0; len1=strlen(str); for(i=0;i<len1;i++){ num[n++]=str[i]-'a'+1; } num[n++]=29; scanf("%s",str); len2=strlen(str); for(i=0;i<len2;i++){ num[n++]=str[i]-'a'+1; } num[n]=0; da(num,n+1,30); calHeight(num,n); initRMQ(n); solve(); } return 0; }
发表评论
-
[树状数组]poj 2299
2014-12-13 20:58 1874题意 求一列数字的逆序数。 思路 ... -
[树状数组]hdoj 1166
2014-12-12 01:21 2题意 http://acm.hdu.edu.cn/ ... -
[树状数组]hdoj 1166
2014-12-12 01:21 853题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 582题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 756i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 853题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 703题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1091题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 581题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 477题意 给出一串数字,m个询问,对于每次询问求出 ... -
[线段树成段更新]hdoj 1698
2014-11-27 21:00 690题意: 对一个线段上的值进行修改,一次可以把[i, ... -
[线段树成段更新]poj 3468
2014-11-27 12:43 665题意: 给出一串n个数,每次操作分为两种,分 ... -
[线段树]poj 2828
2014-11-26 22:02 688题意 n个人插队,每次某个人都会选择插入第i个 ... -
[线段树]hdoj 2795
2014-11-25 20:33 837题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 898题意 给出一列n个数字,每一个数字都和其他 ... -
[后缀数组]acdream 1430
2014-10-16 14:08 503大致题意: 求出一个字符串(len<=1 ... -
[KMP+乱搞]hdoj 4749
2014-10-11 15:22 743大致题意: 求文本串中最多能选出多少子串,使得这 ... -
[KMP]hdoj 4763
2014-10-10 11:39 659题意: 给出一个字符串,问是否存在这样的子串E使得 ... -
[后缀数组][二分]hdu 5008
2014-09-27 10:10 981大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1234大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
后缀数组的应用受到越来越多人的关注,本文详细介绍了后缀数组的基本原理以及LCP—最长公共前缀。最后给出了几道例题及解析。
后缀数组倍增算法实现 + RMQ问题ST算法实现
用倍增算法对后缀数组的实现,其中用rmq实现询问两个后缀的最长前缀。
后缀数组(Suffix Array)标程。采用DA算法。RMQ预处理询问。
内容: 许智磊后缀数组的pdf 本人解说的ppt 制作的mdl 有错误请指正...
RMQ以及LCA:最近公共祖先 解析及P解法 (ZFrom Internet)
rmq-docker-win docker build -t gsxsolutions/rmq:3.5.4 -f .\Dockerfile.3.5.4 . docker build -t gsxsolutions/rmq:3.7.4 -f .\Dockerfile.3.7.4 . docker build -t gsxsolutions/rmq:3.7.5 -f .\Dockerfile....
RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....
RMQ问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。
RMQ.io 您是否要构建可靠且易于编码的连接服务?Rmq.io的任务rmq.io的任务是使RabbitMQ的发布订阅变得容易1,2,3基本原理一个可靠且简单的pubsub并不容易找到。 RabbitMQ是功能强大的消息队列,它具有许多功能,对于...
本科参加ACM竞赛的过程中积累下来的一部分算法模板,和自己在PKU上面做的一部分题目。 模板目录结构: 目录: 动态规划 O(n^2)的最长上升子序列 ... 后缀数组,分三段,分别倒转,字典序最小 AC自动机实现多串匹配
简单的 Rabbit MQ 示例 一个使用 Erlang 客户端库的非常简单的 Rabbit MQ 示例 ... 克隆 rmq_simple cd rmq_simple 使 RABBITMQ_VERSION={Version} 依赖 编译 跑起来 享受 :grinning_face_with_smiling_eyes: !
树状数组的总结 -rmq算法. 用树状数组实现离线rmq
已完成:天真RMQ,更快RMQ(使用nlogn稀疏表) 待办事项:执行±1 RMQ 天真的RMQ输出: (1(2(4..)(5..))(3(6..)(7..))) indexs : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, values : [1, 2, 4, 2, 5, 2, 1, 3,...
最全的RMQ资料,看懂了应该RMQ没问题了
linux环境搭建+hadoop+zk+flume+kafka+mysql+hive+redis+es+Rmq+hbase+spark+storm+azkaban
平衡二叉树 可并优先队列 线段树和树状数组基础 RMQ与LCA
我们会学到RMQ到底是什么东西,并且会知道这样时候的LCA怎么求解,一切尽在其中!