- 浏览: 390644 次
- 性别:
- 来自: 杭州
文章分类
最新评论
-
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 1915题意 求一列数字的逆序数。 思路 ... -
[树状数组]hdoj 1166
2014-12-12 01:21 2题意 http://acm.hdu.edu.cn/ ... -
[树状数组]hdoj 1166
2014-12-12 01:21 895题意 http://acm.hdu.edu.cn/ ... -
[离散化+线段树]poj2528
2014-12-01 23:16 621题意 给出每个海报的位置,问最后没有被完全覆盖 ... -
[线段树区间合并]poj 3667
2014-12-01 11:45 801i题意 和poj1823差不多,加了一个查 ... -
[线段树区间更新]poj 1823
2014-12-01 02:56 899题意 一个旅馆有n个房间,有m次操作,每次操作可 ... -
[线段树]poj 3368
2014-11-29 07:58 753题意 给出一串数字,有m次询问,每次询问[ab ... -
[线段树成段更新]poj 2777
2014-11-28 01:33 1138题意: 一段区间从1-n的初始颜色为1,每 ... -
[线段树]poj 2182
2014-11-27 23:13 616题意: n头牛站队,每头牛都有一个属于[ ... -
[线段树]poj 3264
2014-11-27 21:57 510题意 给出一串数字,m个询问,对于每次询问求出 ... -
[线段树成段更新]hdoj 1698
2014-11-27 21:00 728题意: 对一个线段上的值进行修改,一次可以把[i, ... -
[线段树成段更新]poj 3468
2014-11-27 12:43 707题意: 给出一串n个数,每次操作分为两种,分 ... -
[线段树]poj 2828
2014-11-26 22:02 731题意 n个人插队,每次某个人都会选择插入第i个 ... -
[线段树]hdoj 2795
2014-11-25 20:33 876题意:一个高h宽w的二维空间,每次放进去一个高为1,宽为a的 ... -
[线段树]hdoj 1394
2014-11-24 22:40 939题意 给出一列n个数字,每一个数字都和其他 ... -
[后缀数组]acdream 1430
2014-10-16 14:08 534大致题意: 求出一个字符串(len<=1 ... -
[KMP+乱搞]hdoj 4749
2014-10-11 15:22 785大致题意: 求文本串中最多能选出多少子串,使得这 ... -
[KMP]hdoj 4763
2014-10-10 11:39 699题意: 给出一个字符串,问是否存在这样的子串E使得 ... -
[后缀数组][二分]hdu 5008
2014-09-27 10:10 1031大致题意: 给出一个长度小于100000的字符串 ... -
[线段树,单点更新]hdoj 1754:I Hate It
2012-10-21 21:33 1306大致题意: 给出一个数组,在线更新点的值,查询区 ...
相关推荐
后缀数组是字符串处理中的一种重要数据结构,它在计算机科学特别是文本算法领域扮演着关键角色。后缀数组能够提供一种高效的方式来存储和查询字符串的后缀,这使得它成为解决许多字符串问题的有效工具,例如查找模式...
4. **编辑距离**:后缀数组结合其他数据结构(如LCP数组和RMQ(Range Minimum Query))可以快速计算两个字符串的编辑距离。 5. **AC自动机**:后缀数组是构建AC自动机的基础,用于支持多个模式的并行匹配。 ### ...
本文将深入探讨后缀数组及其相关概念,包括SA(Suffix Array)、Height、RMQ(Range Minimum Query)以及多串匹配。 首先,让我们理解什么是后缀数组(Suffix Array)。后缀数组是字符串的所有后缀按字典序排序后的...
在字符串处理的背景下,后缀数组的k-前缀比较关系、名次数组Rank、基数排序、以及最长公共前缀的RMQ问题都是需要掌握的关键知识点。名次数组Rank实际上是后缀数组的辅助数据结构,用于快速查询某个后缀在排序后的...
根据给定的信息,本文将详细解释“后缀数组C++实现代码”中涉及的重要知识点,包括后缀数组、倍增算法、以及RMQ(Range Minimum Query)问题。 ### 一、后缀数组 #### 1.1 定义 后缀数组是一种数据结构,它存储了...
结合这两个知识点,我们可以构建一个系统,先用倍增算法构建后缀数组,然后利用ST算法实现的RMQ功能来快速查询字符串中某段后缀的最小值,这对于分析字符串性质或者进行特定的字符串搜索任务非常有用。在实际应用中...
### RMQ与LCA:最近公共祖先解析及解法 #### 一、引言 在计算机科学领域,尤其是在算法设计中,“最近公共祖先”(LCA, Least Common Ancestor)和“区间最小值查询”(RMQ, Range Minimum Query)是两个非常重要...
ACM算法讲解 本文将对ACM主要算法进行讲解,涵盖了基本算法、图算法、数据结构、搜索、计算几何学、动态规划和综合题等多方面的知识点。 一、基本算法 ... + 后缀数组、后缀树 + 块状链表 + 哈夫曼树
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....
+ poj1860, poj3259, poj1062, poj2253, poj1125, poj2240 * 最小生成树算法:prim, kruskal + poj1789, poj2485, poj1258, poj3026 * 拓扑排序:poj1094 * 二分图的最大匹配:匈牙利算法 + poj3041, poj3020 * ...
### 后缀数组(Suffix Array)详解 #### 引言 后缀数组是计算机科学领域内一种高效的数据结构,主要用于字符串处理,特别是模式匹配、文本分析等场景。它能够快速定位一个子串在主串中的位置,对于解决复杂的字符...
NOTONLLY的后缀数组模板.cpp RMQ-ST算法.cpp RMQ线段树.cpp SBT.cpp SBT2.cpp splay伸展树.cpp ST表.cpp Treap.cpp Trie树.cpp 二叉堆.cpp 二维线段树.cpp 后缀数组.cpp 后缀数组模板.cpp 块状链表.cpp 左偏树 (2)....
此外,代码中还提到了RMQ(Range Minimum Query,区间最小值查询)版本的后缀数组,这表明可能在处理后缀数组时,也考虑了区间内的最小值查询问题,这对于某些特定的应用场景非常有效。 总结起来,后缀数组是字符串...
- **后缀数组**:构建后缀数组,并计算height数组。 - **最长回文子串预处理**:预处理以每个位置为中心的最长回文子串。 - **结构体数组**:构造一个结构体数组存储每个回文子串的左边界和中心位置,并按左边界排序...
RMQ 动画 这是用于创建文档中说明的动画的应用程序。 这个 repo 是一个简单的应用程序,用于说明 RMQ 可用的动画: rmq(my_view).animations.fade_in rmq(my_view).animations.fade_out rmq(my_view).animations....
12. **后缀数组**:后缀数组是字符串处理中的一种数据结构,用于快速访问字符串的所有后缀,常用于模式匹配和文本分析。 13. **归并树**:归并树(Merge Sort Tree)是基于归并排序构建的数据结构,用于高效地处理...
通过了解后缀数组,我们可以解决如poj3261这样的模板题。 对于后缀数组的入门,推荐阅读的两篇文章是: 1. https://www.cnblogs.com/nietzsche-oier/articles/6621881.html 2. ...
`compat-libstdc.rpm` 文件是Oracle数据库安装过程中经常遇到的一个依赖组件,它主要用于解决旧版本的GNU标准C++库(libstdc++)与新版本操作系统之间的兼容性问题。在Linux环境中,Oracle数据库可能需要特定版本的...
- 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...