位置:首页 » 技术 » 后缀数组--(最长公共前缀)

后缀数组--(最长公共前缀)

日期:2013-06-01 阅读:0num
Advertisement

问题描述:给一个字符串,询问某两个后缀的最长公共前缀。

解析:当然用后缀数组最方便,在后缀数组中有很多重要的定义和性质,现在我们来认识一些:

定义:LCP(i,j)=suffix(SA[i])与suffix[SA[j]]的最长公共前缀长度,即排号序后的后缀中第i名和第j名的最长公共前缀长度。

然后我们再用一个重要的性质就可以求出LCP(i,j)了,性质描述:LCP(i,j)=min{LCP(k-1,k)} i<k<=j

而对于LCP(k-1,k)我们有height数组啊,比如我们要求suffix(i)和suffix(j)的最长公共前缀,就相当于求height[rank[i]]到height[rank[j]]之间的最小值。

至于区间求最小值,ST是个很好的选择啊,到此问题圆满解决。

相关文章
  • 后缀数组--(最长公共前缀)

    问题描述:给一个字符串,询问某两个后缀的最长公共前缀. 解析:当然用后缀数组最方便,在后缀数组中有很多重要的定义和性质,现在我们来认识一些: 定义:LCP(i,j)=suffix(SA[i])与suffix[SA[j]]的最长公共前缀长度,即排号序后的后缀中第i名和第j名的最长公共前缀长度. 然后我们再用一个重要的性质就可以求出LCP(i,j)了,性质描述:LCP(i,j)=min{LCP(k-1,k)} i<k<=j 而对于LCP(k-1,k)我们有height数组啊,比如我们要求suffi

  • 后缀数组之最长公共前缀

    #include #define maxn 100 int main() { int rank[maxn],height[maxn],sa[maxn]= {0,3,1,4,2},s[maxn]= {1,2,3,2,3};//s串可以看成abcbc int i,j,k=0; for(i=0; i rank[sa[i]]=i; for(i=0; i { if(rank[i]==0)//当rank[i]=0的时候也就是求height[0]没有意义所以直接把height[0]=0,k也变为0就行了 {

  • 滴血小结(java版):最长公共子序列(子串)、最长公共回文子序列(子串)、最长公共前缀(后缀)

    滴血总结(java版):最长公共子序列(子串).最长公共回文子序列(子串).最长公共前缀(后缀) 1,最长公共前缀问题 有点类似冒泡算法,每次都要找最小的串的长度,然后进行截取,代码如下 public String longestCommonPrefix(String[] strs) { if(strs.length==0) return ""; String s=strs[0]; for (int i = 1; i < strs.length; i++) { if(s.leng

  • URAL 标题1517. Freedom of Choice(后缀数组,求公共最长串) URAL 标题1517. Freedom of Choice(后缀数组,求公共最长串)

    URAL 题目1517. Freedom of Choice(后缀数组,求公共最长串) 1517. Freedom of Choice Time limit: 2.0 second Memory limit: 64 MB Background Before Albanian people could bear with the freedom of speech (this story is fully described in the problem "Freedom of speech&qu

  • 【LeetCode-口试算法经典-Java实现】【014-Longest Common Prefix(最长公共前缀)】 【LeetCode-口试算法经典-Java实现】【014-Longest Common Prefix(最长公共前缀)】

    [LeetCode-面试算法经典-Java实现][014-Longest Common Prefix(最长公共前缀)] [014-Longest Common Prefix(最长公共前缀)] [LeetCode-面试算法经典-Java实现][所有题目目录索引] 原题 Write a function to find the longest common prefix string amongst an array of strings. 题目大意 写一个函数找出一个字串所数组中的最长的公共前缀.

  • LeetCode 14 Longest Common Prefix(最长公共前缀) LeetCode 14 Longest Common Prefix(最长公共前缀)

    翻译 写一个函数(或方法)来寻找一个字符串数组中的最长公共前缀. 原文 Write a function to find the longest common prefix string amongst an array of strings. 释义 abcdefg abcdefghijk abcdfghijk abcef 上面的字符串数组的最长公共前缀就是abc. 思考 如下图所示,第一步就是要找出该字符串数组中的最短字符串的长度及其序列. 第二步,用for循环从第一个字符串到最后一个字符串依

  • 面试题[后缀数组]: 最长重复子串

    题目:给定一个字符串,求出最长重复子串. 这个题目可以用后缀数组来解:对后缀数组排好序,这样重复的子串就在相邻的后缀中找就可以了.我的C++代码实现如下: class Solution { public: string LongestRepeatingSubstring(string str) { size_t len = str.size(); vector SuffixArray(len); for (size_t i = 0; i < len; ++i) SuffixArray[i] =

  • POJ 1743 Musical Theme(后缀数组求不可堆叠最长重复子串)

    POJ 1743 Musical Theme(后缀数组求不可重叠最长重复子串) 转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove 题目:给出一些音符,求出最长的重复出现的旋转长度. http://poj.org/problem?id=1743 从题目中的意思可以知道,只要满足相邻的差相等便可以了,那我们建立一个相邻并非的数组,题目要求的便是求最长的重复子串长度,而且不可重叠. 由于 相邻差可

  • POJ 1743 Musical Theme(后缀数组求不可重叠最长重复子串)

    题目:给出一些音符,求出最长的重复出现的旋转长度. 从题目中的意思可以知道,只要满足相邻的差相等便可以了,那我们建立一个相邻并非的数组,题目要求的便是求最长的重复子串长度,而且不可重叠. 由于 相邻差可能为负,则统一加上100,转变为0-200之间的数即可. 之后求出height数组,表示的是相邻后缀的最长公共前缀. 二分答案,然后进行判定 按height就可以对后缀进行分组,height如果大于长度,则我们需要判断是否重叠,通过sa的差值即可.详见代码 [cpp] #include<iostr

  • URAL 1297. Palindrome(输出最长回文子串-后缀数组)

    URAL 1297. Palindrome(输出最长回文子串--后缀数组) Input The input consists of a single line, which contains a string of Latin alphabet letters (no other characters will appear in the string). String length will not exceed 1000 characters. Output The longest subs

  • poj 1743 Musical Theme 【后缀数组】【求不可堆叠最长重复子串】

    poj 1743 Musical Theme [后缀数组][求不可重叠最长重复子串] Musical Theme Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 21913 Accepted: 7494 Description A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the range

  • POJ 1743 Musical Theme 不可堆叠最长重复字串(后缀数组)

    POJ 1743 Musical Theme 不可重叠最长重复字串(后缀数组) 点击打开链接 Musical Theme Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 16969 Accepted: 5817 Description A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the r

  • URAL 1297 后缀数组:求最长回文子串

    思路:这题下午搞了然后一直WA,后面就看了Discuss,里面有个数组:ABCDEFDCBA,这个我输出ABCD,所以错了. 然后才知道自己写的后缀数组对这个回文子串有bug,然后就不知道怎么改了. 然后看题解,里面都是用RMQ先预处理任意两个后缀的最长公共前缀,因为不太知道这个,所以又看了一下午,嘛嘛-- 然后理解RMQ和后缀一起用的时候才发现其实这里不用RMQ也可以,只要特殊处理一下上面这个没过的例子就行了,哈哈--机智-- 不过那个国家集训队论文里面正解是用RMQ做的,自己还得会和RMQ一

  • URAL - 1297 Palindrome(后缀数组求最长回文子串)

    Description The "U.S. Robots" HQ has just received a rather alarming anonymous letter. It states that the agent from the competing ?Robots Unlimited? has infiltrated into "U.S. Robotics". ?U.S. Robots? security service would have alrea

  • 后缀数组练习

    后缀数组习题 原文:http://hi.baidu.com/lewutian/blog/item/4d098138d29c34f9b311c725.html 单独把它列出来是因为这个东西真的很神奇~~~ 后缀数组经典思想:多串合并+二分答案+最优性--->可行性 例 1 :最长公共前缀 给定一个字符串,询问某两个后缀的最长公共前缀. // 直接套用,ans=min( height[ i ] )+rmq k<i<=j 例 2 :可重叠最长重复子串 给定一个字符串,求最长重复子串,这两个子串

  • POJ 3415 Common Substrings(后缀数组+单一栈)

    POJ 3415 Common Substrings(后缀数组+单调栈) 转载请注明出处,谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove 题目:求出长度不小于k的公共子串个数 http://poj.org/problem?id=3415 继续论文上的题目. 计算A的某个后缀与B的某个后缀的最长公共前缀长度,如果长度L大于k,则加上L-k+1组. 将两个字符串连接起来,中间用一个没有出现的字符分开.(这是一

  • 后缀数组兑现的倍增算法和DC3算法

    后缀数组实现的倍增算法和DC3算法 /************************************************ 数据结构:后缀数组(Suffix_Array); 子串: 字符串S的子串r[i..j],i≤j,表示r串中从i到j这一段, 也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串; 后缀: 后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串; 字符串r的从第i个字符开始的后缀表示为Suffix(i),也就是Suffix(i)=r[i...len(

  • POJ 3693 反复次数最多的连续重复子串 后缀数组

    POJ 3693 重复次数最多的连续重复子串 后缀数组 题目大意就是求重复次数最多的连续重复子串.例如abababc 答案就是ababab 因为ab连续出现的次数最多 并且题目还要求输出字典序最小的 比如abababcdcdcd ababab和cdcdcd都符合要求 但是ababab字典序小 具体做法参见罗穗骞的论文 穷举子串的长度L,然后求长度为L的子串最多出现几次 首先连续出现一次是肯定的,所以只考虑出现两次及以上的情况 假设在字符串中出现了两次,记这个重复了两次L长度子串的子串为S. 那么

  • POJ3693:Maximum repetition substring(后缀数组+RMQ)

    Description The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1. Given a

  • HDU 3518 Boring counting(后缀数组啊 求字符串中不重叠的重复出现最少两次的子串的个数)

    HDU 3518 Boring counting(后缀数组啊 求字符串中不重叠的重复出现至少两次的子串的个数) 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3518 Problem Description 035 now faced a tough problem,his english teacher gives him a string,which consists with n lower case letter,he must figur

最新文章
  • 角色设计的40个顶级技巧(上篇):动物角色 角色设计的40个顶级技巧(上篇):动物角色

    无论是创造动物角色还是近似人的角色,心中充满自信是让角色令人信服的关键.下面,一些世界顶级的角色设计师将会分享他们对于创意设计的一些注意事项. 无中岂能生有.这是句老话但却是至理名言,对于角色设计来说,更是如此.每一个角色它都需要有一个故事设定,一个世界观以及一个存在的意义. 一旦你明白了这个,那么你在进行设计时,就要反问自己:"它的身体应该是什么样的?他需要露出一口锋利的牙齿吗?需要什么其他的装饰吗?"根据这些你就能设计出一个令人信服的角色了,而剩下的那就只是纯粹的技术活了. 当然,

  • 二十四节气结束季——大寒 二十四节气结束季——大寒

    二十四节气结束季--大寒 大寒是二十四节气之尾,也是冬季即将结束之季,隐隐中已可感受到大地回春的迹象,我们即将送走冬季,迎来温暖的春天. 大寒是二十四节气的最后一个,此时正值生机潜伏.万物蛰藏的冬季,人体的代谢也处于相当缓慢的时候.大寒养生要顺应冬季"藏"的原则,最简单的方法是早睡晚起,每天多睡1小时.对于上班族特别提倡早睡1小时,老年人尤其要注意不宜过早起床,晨练要推迟一些,最好等到太阳出来以后再进行户外锻炼,同时应当做好充分的运动前热身准备. 大寒节气的到来正值全年最冷的时候,有一

  • 黄褐斑怎么去除 黄褐斑怎么去除

    黄褐斑怎么去除 黄褐斑的出现多数与内分泌有关,尤其是和女性的雌激素水平有关,月经不调.妊娠.服避孕药或肝功能不好以及慢性肾病都可能出现黄褐斑,黄褐斑大多出现在四十岁以上的女性.满脸的班点影响美观,令女性失去自信,同时也是身体欠佳的表现.黄褐斑怎么去除?去斑的方法很简单,只要通过几道食疗妙方,就可以轻松帮女性们排解烦忧. 1.薏苡粥 原料:猪肾1对.山药100克.粳米200克.薏苡仁50克.水适量. 做法:猪肾去筋膜.臊腺,切碎,洗净.与去皮切碎的山药.粳米.薏苡仁.水一起.用小火煮成粥,加调料调

  • 描写露珠的好词

    二字词: 露水 露珠 白露 甘露 朝露 夜露 晶莹 露珠 晶莹 露水 湿发 透亮 闪烁 四字词: 白露沾草 晨霜晓露 垂露欲滴 露水滋润 露垂草弯 露珠闪烁 露珠滚动 五彩露珠 露珠闪亮 露水沾衣

  • 东芝Satellite U845T评测 东芝Satellite U845T评测

    东芝Satellite U845T(型号为S4165) 东芝Satellite U845T(型号为S4165)主要参数信息: · 处理器:采用酷睿i5-3337U处理器 · 内存:6GB RAM,最大可升级至8GB · 硬盘:128GB mSATA SSD · 屏幕:14英寸,1366*768分辨率 · 系统:Windows 8 · 芯片组及显卡:英特尔HM77 Express,集成HD Graphics 4000 显卡 · 无线网络:Wireless-N 2200网卡,支持802.11b/g/

  • 国际汉语教师资格证哪家强?专家为你解析 国际汉语教师资格证哪家强?专家为你解析

    摘要:" 玛瑞欧教育_IMCPI国际汉语教师资格证"为满足日益增长的汉语学习需求,建立了一套完善.科学.规范的国际汉语教师认证标准体系,旨在提高汉语教师的专业素质和教学水平,培养.培训合格的专业国际汉语教师. 随着中国经济的迅猛发展,越来越多的外国人来中国淘金,中国在世界舞台的影响日渐强大,全世界范围内兴起一股学习汉语的热潮.在中国一线城市北京上海更是存在巨大的对外汉语商机,作为国际化大都市,每时每刻,北京上海都上演着中西方经济.文化.语言的激情碰撞,而一线城市的白领们因为特定的工作环

  • 不用插件 直接启动WordPress的Gzip网页压缩 不用插件 直接启动WordPress的Gzip网页压缩

    网页想要速度再快,除了平时做好网页优化之外,如果网页输出时可以经过压缩,那可以让网页加速开启,减少等待时间,这项功能就叫做Gzip网页压缩.在WordPress中虽然有插件可以启动Gzip网页压缩,不过能通过几句语法来达到网页压缩,这样不是更好吗?其实在PHP中,有一句语法是可以开启Gzip的,只要加在网页输出的前端即可. 除此之外,也可以通过.htaccess来调整系统,启动Gzip所需的设定,让网站达到加速的需求,若是可以启动Gzip除了输出时网页比较小,接收者可以很快开启网页之外,也可以省

  • 三国志13特殊兵种获得方法分享 三国志13特殊兵种获得方法分享

    在三国志13的这一款游戏当中特殊兵种是某些聚落所附带的,很多嫌麻烦的玩家也可通过修改的方法来解锁,今天小编就给大家带来了三国志13特殊兵种修改获得方法,下面就来跟着小编一起看一下吧. 给各位三国志13的玩家们来详细的解析分享一下特殊兵种的获得方法. 方法分享: 自己测试了一下.刚开档在平原.特殊兵种出现4个.弓骑兵和青州还没出现. 所有特殊兵种只需要兵种熟练度.6个部落全都改成别的加成. 算是给自己增加一个难度吧. 具体方法.V大修改器.修改剧本.到兵种内栏里.把6个特殊兵种的部落从属取消.必要

  • jquery validate remote应验规则使用心得

    jquery validate remote验证规则使用心得 remote验证,默认接受server返回 true,false .且message的定义只有一种错误情况.你无法定义2种或者2种以上的错误信息返回. 这就是问题所在. 修改validate源码可以做到server端返回其他参数.

  • axis2开发webservice之将Spring的装配JavaBean发布成WebService axis2开发webservice之将Spring的装配JavaBean发布成WebService

    前些阵子刚好学会了spring,现在来把axis2和spring结合一下,这也是做企业开发的时候必须的,结合教程来学习一遍. 在现今的Web应用中经常使用Spring框架来装载JavaBean.如果要想将某些在Spring中装配的JavaBean发布成WebService,使用Axis2的Spring感知功能是非常容易做到的. 在本文的例子中,除了<Tomcat安装目录>\webapps\axis2目录及该目录中的相关库外,还需要Spring框架中的spring.jar文件(这里是基于spri

热门推荐
  • 什么是世界接吻日? 什么是世界接吻日? 7月6日国际接吻日,又称世界接吻日(International Kissing Day)这个节日首先由英国人发起,二十年前得到联合国的批准.接吻是一种古老而风行的示爱方式,也是一种甜蜜的享受. 接吻礼仪溯源 接吻的历史始于大约公元前3000年,古人们在膜拜众神时都要亲吻他们.古罗马时期,不仅与朋友和家庭成员接吻,还要与商人和路人接吻,以此表示对他们的欢迎.中世纪这种见面礼不仅要受到人际关系的约束,还要受到社会阶层的约束.社会地位越低,亲吻距离脸部就越远.对于与自己地位相等的人吻嘴唇,比自己地位高
  • 网站建设过程中如何借鉴别人的策划技巧? 网站建设过程中如何借鉴别人的策划技巧? 这段时间新的域名正在备案中,一种在忙碌对网站其他方面的一些事情,例如购买空间,模板之类的事情.对于做优化的我们,可能对于程序开发之类的事情不太关心,然而我们还是要懂得基础的HTML+CSS这些.对于我自己来说也不是什么程序高手,就是会用现成的CMS进行套标签之内的事情.在这里,还是提醒朋友们,选择现成CMS,最好选择自己比较熟悉,擅长的程序,如果你擅长织梦CMS就建议在之后做网站的时候,用织梦CMS;擅长帝国CMS就用帝国CMS,这是对网站程序给出的一点建议. 这里就不在把过多的话,放在网站程序
  • 秋冬季节为什么会易出现落枕? 秋冬季节为什么会易出现落枕? 长期伏案工作,颈项部位的肌肉长时间被牵张,会导致肌肉劳损. 还有些人睡熟后姿势不正确,如长时间保持一个姿势;枕头选的高低软硬不合适,使颈部过于拉伸或过于弯曲,也容易造成落枕. 如果落枕了,但没出现手脚麻木等症状,最好躺在床上不要乱动,让肌肉慢慢恢复.倘若超过24小时,还是没有好转,就要及早就医.而除了觉得脖子僵硬之外,还感到手脚麻木,则很有可能是颈椎病,最好直接去医院. 最后,教给大家3个冬天预防落枕的小方法:多用暖水袋敷肩颈部;出门带上围巾,给肩颈保暖;多做颈部运动,前后左右转一转,一天做5-
  • 小米5后盖怎么打开? 小米5后盖怎么打开? 下面,小编就来教大家小米5后盖怎么打开. 小米5后盖怎么打开? 由于小米5采用了双面玻璃+金属边框设计,机身表面看不到任何固定螺丝,属于一款不可拆卸后盖手机,第一感觉给人无从下手. 对于双面玻璃+金属边框设计的手机,拆机要么是从屏幕入手(难度很大),要么是从后盖入手(比较简答).而小米5则延续了小米Note系列设计风格,拆机比较简答,因为可以直接从后盖入手,以下是小米5后盖开启方法. 准备工具:吸盘 由于小米5后盖采用卡扣式设计,并没有采用胶水固定,因此只要使用吸盘轻轻一吸.一拉,后盖就可以轻松
  • win8系统屏幕显示方向调节教程 win8系统屏幕显示方向调节教程 一般情况下我们的电脑屏幕都是横向显示的,有些时候如果这么显示就会有些不是很方便,而win8系统的屏幕显示方向是可以调节的,这时候我们只要经过几部简单设置就能调节到我们需要显示的方向.下面百事网小编就和大家分享一下设置教程. 1.鼠标右击桌面空白处,然后在弹出菜单中选择屏幕分辨率. win8系统屏幕显示方向设置教程 2.在方向栏,我们就可以根据需要设置的屏幕的显示方向了,选择完成之后点击确定. win8系统屏幕显示方向设置教程 3.确定之后会弹出一个对话框,我们直接选择保存更改即可,否曾会在15秒