- 浏览: 377915 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
wsyzyrxp:
非常感谢 兄弟 帮了我大忙
[opengl]弹簧质点法模拟柔性布料以及椭球碰撞的opengl实现 -
mingdry0304:
[opengl]彩色立方体旋转 -
tyfengyu:
我刚刚更改的代码加上了标准差stdVal,故recoMat应该 ...
[python]用python实现的pca算法 -
tyfengyu:
python的pca代码有2处错误:1.finalData = ...
[python]用python实现的pca算法 -
暴风雪:
McFlurry 写道前排(凑字数)!擦你怎么摸来这里的
诈尸总结
大致题意:
给出一个字符串,求出内部循环次数最多的子串。如果答案有多个,输出字典序最小的。
大致思路:
先穷举长度L,然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的,所以这里只考虑至少2 次的情况。假设在原字符串中连续出现2 次,记这个子字符串为S,那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远,记这个总长度为K,那么这里连续出现了K/L+1 次。最后看最大值是多少
以上内容摘自罗穗骞论文,花了好几天理解照着上面敲出来的,比赛时如果碰到这样的题肯定会被爆。不过ac之后又加深了对后缀数组的理解
#include<iostream> #include<cstdio> #include<vector> #include<cstring> using namespace std; const int nMax =1000012; 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]); } char str[nMax]; int ans[nMax]; int main(){ int i,j,n,cas=0; 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&&str[0]!='#'){ n=strlen(str); for(i=0;i<n;i++){ num[i]=str[i]-'a'+1; }num[n]=0; da(num, n + 1,30); calHeight(num,n); initRMQ(n); int l,r,t,k,maxx=-1,a; for(l=1;l<n;l++){ //枚举长度 for(i=0;i+l<n;i+=l){ k=lcp(i,i+l); r=k/l+1; t=l-k%l; t=i-t; if (t>=0&&k%l!=0){ if(lcp(t,t+l)>=k) r++; } if(r>maxx){ a=0; maxx=r; ans[a++]=l; } if(a==maxx){ ans[a++]=l; } } } int start,b=0,c; for(i=1;i<=n&&!b;i++){ //sa数组是保证字典序的神器啊 Orz for(j=0;j<a;j++){ int tl=ans[j]; if(lcp(sa[i],sa[i]+tl)>=(maxx-1)*tl){ start=sa[i]; l=tl*maxx; b=1; break; } } } printf("Case %d: ",++cas); for (int i=0;i<l;i++) printf("%c",str[start+ i]); printf("\n"); } return 0; }
发表评论
-
[树状数组]poj 2299
2014-12-13 20:58 1873题意 求一列数字的逆序数。 思路 ... -
[树状数组]hdoj 1166
2014-12-12 01:21 2题意 http://acm.hdu.edu.cn/ ... -
[树状数组]hdoj 1166
2014-12-12 01:21 849题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 581题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 750i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 848题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 697题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1087题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 579题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 468题意 给出一串数字,m个询问,对于每次询问求出 ... -
[线段树成段更新]hdoj 1698
2014-11-27 21:00 684题意: 对一个线段上的值进行修改,一次可以把[i, ... -
[线段树成段更新]poj 3468
2014-11-27 12:43 661题意: 给出一串n个数,每次操作分为两种,分 ... -
[线段树]poj 2828
2014-11-26 22:02 686题意 n个人插队,每次某个人都会选择插入第i个 ... -
[线段树]hdoj 2795
2014-11-25 20:33 832题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 894题意 给出一列n个数字,每一个数字都和其他 ... -
[后缀数组]acdream 1430
2014-10-16 14:08 501大致题意: 求出一个字符串(len<=1 ... -
[KMP+乱搞]hdoj 4749
2014-10-11 15:22 741大致题意: 求文本串中最多能选出多少子串,使得这 ... -
[KMP]hdoj 4763
2014-10-10 11:39 657题意: 给出一个字符串,问是否存在这样的子串E使得 ... -
[后缀数组][二分]hdu 5008
2014-09-27 10:10 977大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1230大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
后缀数组的应用受到越来越多人的关注,本文详细介绍了后缀数组的基本原理以及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.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问题是指:对于长度为n的数列A,回答若干询问RMQ(A,i,j)(i,j<=n),返回数列A中下标在[i,j]里的最小值下标。
树状数组的总结 -rmq算法. 用树状数组实现离线rmq
linux环境搭建+hadoop+zk+flume+kafka+mysql+hive+redis+es+Rmq+hbase+spark+storm+azkaban
RMQ是英文Range Maximum(Minimum) Query的缩写,顾名思义是用来求某个区间内的最大值或最小值,通常用在要多次询问一些区间的最值的问题中。
平衡二叉树 可并优先队列 线段树和树状数组基础 RMQ与LCA
已完成:天真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,...
2015_ble_to_rmq ble_to_rmq sample说明: 将此程式编译过的jar档放到respberry pi上执行,可以搜寻附近的BLE Device并与之连接,将透过dongle送到respberry pi的ble讯息印出来。