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

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

日期: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

最新文章
  • Nova中的系统状态分析

    写此文的目的 转眼间OpenStack已经发展到了K,马上L版本开发周期也要开始了.记得我最早接触的是OpenStack的E版本,时间过去了2年多,OpenStack社区仍然如火如荼,OpenStack玩家,特别是重量级玩家越来越多,通过每次OpenStack峰会的报道.社区的user survey以及圈里的分享,我们发现OpenStack的生产环境部署也越来越多,但是相信很多企业,很多人,在使用OpenStack的过程中仍然很痛苦.安装部署困难,系统复杂性,过于灵活的架构,眼花缭乱的配置项,特

  • 一个很简单问题:怎么存 URL?

    具体的说,是否将unicode的percentage-encoding存进数据库? 换而言之,是存: http://example.com/%E4%BD%A0%E5%A5%BD 还是: http://example.com/你好 我的原提问,细节在上面: http://stackoverflow.com/questions/30526880/should-url-be-stored-in-encoded-or-decoded-form --cut-- chairuosen在2016-05-09

  • 大智慧使用技巧

    大智慧证券信息平台是一套用来进行行情显示.行情分析并同时进行信息即时接收的超级证券信息平台.面向证券决策机构和各阶层证券分析.咨询.投资人员,并特别关注广大股民的使用习惯和感受. 敲打"60"加回车,即可进入涨跌幅大小排行. 敲打"80"加回车,即可进入综合指标排行. 大盘风云.板块起伏.个股动向.热点动向.媒体精华尽在59+回车的实时解盘. 考虑流通股股本大小,是投资者在操作股票时重要一个因素,大智慧营业部板块下,"29"加回车即可进入流通股大

  • 实例分析网站优化方案

    春节后由于忙于生活琐事一直没有开始工作,所以文章更是写的少的可怜.本来想写一篇年底总结来着,但是打开博客点击"新建文章"后却又一个字都不想打,看来是休假休的人变得更懒了.既然懒的对过去总结,那我还是开始手头的工作吧,毕竟还有个肚子要吃饭,不工作怎么行?上午接到一个单子:银杏树价格网(www.yinxingshu.cn)的关键词优化.一个人工作也怪无聊的,而且我个人的力量和知识有限.那就跟大家共同来分析一下这个网站吧,人多力量大嘛.我先用自己的水准来分析一下这个网站,当做是抛砖引玉.有分

  • 表格格式转换救助

    从表1中抽取数据,变成表2的表格格式. 表1的数据是从Access中取出来的,如果可以在Access中形成表2格式的查询也可以 表1如下: ID 日期 仓库 入库 出库 1 200901 A 20 10 1 200901 B 30 20 1 200902 A 20 10 1 200902 B 30 20 1 200903 A 20 10 1 200903 B 30 20 1 200904 A 20 10 1 200904 B 30 20 1 200905 A 20 10 1 200905 B 3

  • 逛街购物不怕宰 360好搜推出“比价神器”码上买 逛街购物不怕宰 360好搜推出“比价神器”码上买

    "大哥,您太能砍了!这价我进都进不来!"."唉算了,为了开个张,就赔钱卖给你吧!"经常逛街购物的人,对这些话都似曾相识.但俗话说,"买的不如卖的精",当你在为砍价成功而得意,觉得占了大便宜时,也许商家正在为又蒙了一个外行而偷乐.为了让价格更透明,用户少花冤枉钱,360旗下好搜低调上线了一款扫码比价APP--码上买,这款产品刚一问世,就凭借白领尤其是女性购物人群中的良好口碑,在各大应用商场获得数十万次下载,好搜搜索指数更是从0飙升到接近5000.

  • 蛤蟆吐蜜的做法

    材料: 面粉500克,豆沙馅750克,芝麻仁50克,小苏打粉4克,老酵面100克. 蛤蟆吐蜜的介绍:此小吃因形似圆鼓的蛤蟆而得名. 蛤蟆吐蜜的特色:外酥里软,香甜可口. 教您蛤蟆吐蜜怎么做,如何做蛤蟆吐蜜 1.盆内加面粉.老酵面.小苏打粉.清水和成面团,略饧片刻. 2.饧好的面团搓成长条,摘成约25克一个的小面剂,擀成圆皮,包入适量豆沙馅,把口封严捏牢,按扁,即成饼坯. 3.饼坯刷少量水粘上芝麻,入炉烤熟.饼熟后则裂开,露出豆沙馅. 蛤蟆吐蜜的制作要领: 1.面团要揉匀饧透,揉至光滑为宜: 2.

  • 土豆逆客手机官网地址 土豆逆客手机官网地址

    据悉,这款手机配备了5英寸720P屏幕,搭载搭载1.5GHz四核处理器(或为MT6732四核64位),拥有2GB RAM和16G ROM,运行Android 4.4.4系统. 近日,逆客影像手机官方表示,本月24日,由土豆和朵唯合作的逆客手机将亮相北京举行的新品发布会.届时绿茶小编胖胖将会为大家提供官网地址. 注:更多精彩教程请关注本站手机教程栏目,本站手机数码群:296605639欢迎你的加入

  • Javascript学习笔记之 函数篇(三) : 闭包和引用

    Javascript 中一个最重要的特性就是闭包的使用.因为闭包的使用,当前作用域总可以访问外部的作用域.因为 Javascript 没有块级作用域,只有函数作用域,所以闭包的使用与函数是紧密相关的. 模拟私有变量 代码如下: function Counter(start) { var count = start; return { increment: function() { count++; }, get: function() { return count; } } } var foo

  • linq 分组 查询返回count 值的有关问题

    linq 分组 查询返回count 值的问题. 我用join 查询和DefaultIfEmpty 返回一个相册中有多少张照片. 但是关键的来了,新建相册,查询,因为相册里此时没有照片,查出的是null值,linq把null值也认为有值 我用Count()方法返回的相片数总是1 当然如果相片数超过1了 数量显示正常. 请问有什么解决办法? ------解决方案-------------------- count()也可加條件->count(o=>o.photo.HasValue)或count(o

热门推荐
  • iPhone5S支持以旧换新吗? iPhone5S支持以旧换新吗? 苹果于2013年8月30号起在Apple Store内推出一项全新服务:iPhone用户可以将他们当前的机器抵值来换购新机.这项计划名为iPhone回收再利用计划(iPhone Reuse and Recycle Program).在2013年9月份苹果将会大规模推广这一全新服务. 这项服务将适用于普通消费者已经企业用户,其细节已经出炉: 1)消费者告知Apple Store员工其愿意购买一部新iPhone同时出让当前的iPhone.新iPhone必须是一部合约机,此外也必须当场激活. 2)Ap
  • 苹果iPhone5S概念图再曝光 或9月发布 苹果iPhone5S概念图再曝光 或9月发布 苹果iPhone 5S概念图 随着苹果新一代iPhone的上市在即,iPhone 5S和廉价版iPhone受到了果粉们的疯狂追捧.如今,美国<国际财经日报>再次曝光了一张iPhone 5S的概念图. 从曝光的概念图来看,iPhone 5S的外观和目前的iPhone5基本一样,不过在配置上,iPhone5S作出了很多升级,比如新的A7处理器,更大容量的电池.两个LED闪光灯.指纹传感器和支持慢动作模式的镜头等5大特征,这也是根据之前曝光的诸多消息能够发现的比较靠谱的特色. 作为iPhone 5的
  • LOL10.22美测更新 新皮肤和新赛季载入框一览 LOL10.22美测更新 新皮肤和新赛季载入框一览 <英雄联盟>美测服今天更新了一些新的内容,下个赛季的载入框将会有很大的变动,而且三款新皮肤也在不断的调整当中,我们一起来看下美测服今天更新的内容吧. 英雄方面,增加了新英雄"Illaoi"的选择英雄语音,是一段葡萄牙语片段. 美术方面,加入了本轮新皮肤主题原画;增加了六款新召唤师头像;加入了全新的游戏载入时的英雄边框;丧尸努努的纹身回归. 新英雄相关文件 在今日补丁中,增加了新英雄"Illaoi"的选择英雄语音,是一段葡萄牙语片段. 翻译成中文的意思是:
  • 常喝牛奶对人体的九大好处 常喝牛奶对人体的九大好处 牛奶是人们生活中很常见的一种食物,它含有丰富的营养物质,非常受人们的喜爱.那么,在生活中经常饮用牛奶对人体都有哪些还出呢?牛奶在什么时候和对人体好呢?今天小编就来给大家介绍一下关于牛奶的健康小常识.大家请看下文. 本站阅读配图 日常生活健康常识 1.稳定血压 牛奶中富含丰富的钾离子,钾离子可促进人体动脉血管壁的稳定能力. 2.防治心脏病 喝牛奶还可防治高血压和心脏病. 3.防中毒 可以阻止人体吸收食物中有毒的金属铅和镉. 4.提高免疫力 牛奶是增强免疫系统功能的一个很好的食物,良好的免疫力可以有
  • 荣耀畅玩4C怎么省电? 荣耀畅玩4C怎么省电? [荣耀畅玩4C省电方法分享] 1.禁用Wi-Fi无线网 WiFi费电比3G网络要厉害多,平时可以禁用,需要时再打开即可. 2.禁用安卓手机蓝牙功能 蓝牙耗电厉害,基本除了传输数据很少用到,因此一般不建议开启. 3.选择省电技术的手机 使用华为手机自带的"省电管理"功能,选择大容量电池并特有省电设计的手机. 4.尽量不使用动态壁纸 使用动态壁纸会消耗很多电量,若不追求酷炫建议不使用. 5.减少屏幕待机时间 如果不影响正常使用,可把屏幕待机时间设置为一分钟或更短. 6.关掉魅影触控的8个字
  • 科学家发现超级宜居星球  外星人高度文明远超人类 科学家发现超级宜居星球 外星人高度文明远超人类 据美国宇航局官方最新消息,美国宇航局旗下的开普勒空间望远镜再次发现一批星球,数量达到230多个,这些星球候选者被认为是系外行星.它们遍布在其他恒星系统中,在其他系外行星上,也有所谓的太阳和月亮,唯一不同的是行星的表面环境与地球不太一样,有些是1000多摄氏度的酷热世界,有些是极度严寒的星球. 美国宇航局科学家玛吉斯-斐乐指出,地外还有数十亿与地球类似的星球存在,那些世界也有其他物种. 开普勒空间望远镜目前已经进入了K2任务阶段,可对数万光年外的恒星进行观测.在美国天文学会第227次会议上,天文学