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

后缀数组之最长公共前缀

日期:2015-01-01 阅读:0num
Advertisement

#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就行了
{
k=0;
height[0]=0;
continue;
}
if(k)
k--;
j=sa[rank[i]-1];
/*
当rank[k]不等于0的时候,rank[i]-1计算出的是上一个排名,通过sa数组找出上一个排名的起始坐标
*/
printf("%d %d %d\n",rank[i],i,j);
while(s[i+k]==s[j+k])
k++;
/*
仔细体会i和j的关系还有后缀i控制的字符的个数
上面的while循环其实是当k=0的时候才进行的当排完循序后后缀k和后缀i-1相邻即(排在后缀i-1的前一个的是后缀k),后缀k
和后缀i-1分别删除首字符之后得到后缀k+1和后缀i,因此后缀k+1一定排在后缀i的前面(相邻),并且最长公共前缀长度为后缀k和
后缀k和后缀i-1的最长公共前缀-1即h[i-1]-1举个例子:
字符串abcbc的后缀为:
0 abcbc
1 bcbc
2 cbc
3 bc
4 c
排完序后为
0 abcbc
3 bc
1 bcbc
4 c
2 cbc
当i等于0的时候rank[0]所以height[0]等于0,k=0
当i等于1的时候rank[1]为2,rank[1]-1==1,这个时候比较的是bcbc和排在他前面的后缀bc(i控制的bcbc的下标,j控制的bc的下标),经过while()循环
判断出来的是k=2即最长公共前缀为2
当i等于2的时候rank[2]为4,rank[2]-1==3,这个时候比较的是cbc和排在他前面的后缀c(bcbc和bc都是由i等于1的两个后缀都去掉一个b之后得到的,
这个时候我们就没有必要再去计算了,我们可以直接通过bcbc和bc的最长公共前缀k减去1得到而没必要在去计算了)
当i等于3的时候rank[3]为1,rank[1]-1==0,这个时候比较的是bc和排在他前面的后缀abcbc经过while()循环判断最长公共前缀为0
当i等于4的时候rank[4]为3,rank[4]-1==2,这个时候比较的是c和排在他前面的后缀bc经过while()循环判断最长公共前缀为0
有上述可以总结出当i是由0-n-1所以后缀是由长到短的,又因为当两个串排好序后相邻的时候,都去掉前面的一个后还是相邻的所以我们可以有长的
递推出短的
*/
height[rank[i]]=k;
}
for(i=0; i printf("%d ",height[i]);
puts("");
return 0;
}

相关文章
  • 后缀数组之最长公共前缀

    #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就行了 {

  • 使用后缀数组找寻最长公共子字符串JavaScript版 使用后缀数组找寻最长公共子字符串JavaScript版

    使用后缀数组寻找最长公共子字符串JavaScript版 后缀数组很久很久以前就出现了,具体的概念读者自行搜索,小菜仅略知一二,不便讨论. 本文通过寻找两个字符串的最长公共子字符串,演示了后缀数组的经典应用. 首先需要说明,小菜实现的这个后缀数组算法,并非标准,只是借鉴了其中的思想. 小菜实现的算法,有两个版本,第一个是空间换时间,第二个是时间换空间. 空间换时间版本 1 /* 2 利用后缀数组获取两个字符串最长公共子字符串 3 空间换时间版本 4 @params 5 s1 String,要分析的

  • 后缀数组之最长公共子串 poj 2774

    用后缀数组求两个串的最长公共子串的长度 详见罗穗骞的论文 [cpp] #include <iostream> #include <cstdio> #include <cstring> #include <string> #include <algorithm> #include <cstdlib> #define MAXN 1000005 using namespace std; int r[MAXN]; int wa[MAXN],

  • 滴血小结(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

  • 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循环从第一个字符串到最后一个字符串依

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

    问题描述:给一个字符串,询问某两个后缀的最长公共前缀. 解析:当然用后缀数组最方便,在后缀数组中有很多重要的定义和性质,现在我们来认识一些: 定义: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

  • 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

  • 【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. 题目大意 写一个函数找出一个字串所数组中的最长的公共前缀.

  • POJ 2774 后缀数组:求最长公共子串

    思路:其实很简单,就是两个字符串连接起来,中间用个特殊字符隔开,然后用后缀数组求最长公共前缀,然后不同在两个串中,并且最长的就是最长公共子串了. 注意的是:用第一个字符串来判断是不是在同一个字符中,刚开始用了第二个字符的长度来判断WA了2发才发现. #include #include #include #include #include #include #include #include #include #define mem(a,b) memset(a,b,sizeof(a)) #defi

  • 后缀数组-处置字符串的利器

    后缀数组--处理字符串的利器 后缀数组是处理字符串的有力工具.后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也并不逊色,而且它比后缀树所占用的内存空间小很多. 子串:字符串S的子串r[i..j],i<=j,表示r串中从i到j这一段,也就是顺次排列r[i],r[i+1],...,r[j]形成的字符串. 后缀:后缀是指从某个位置i开始到整个串末尾结束的一个特殊子串.字符串 s 的从第i个字符开始的后缀表示为Suffix(i), 也就是Suffix

  • poj Common Substrings(后缀数组&amp;单一队列)

    poj Common Substrings(后缀数组&单调队列) Common Substrings Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 7082 Accepted: 2355 Description A substring of a string T is defined as: T(i, k)=TiTi+1...Ti+k-1, 1≤i≤i+k-1≤|T|. Given two strings A, B and

  • 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 3261 Milk Patterns 求可堆叠的 k 次最长重复子串(后缀数组)

    POJ 3261 Milk Patterns 求可重叠的 k 次最长重复子串(后缀数组) 点击打开链接 Milk Patterns Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 9361 Accepted: 4218 Case Time Limit: 2000MS Description Farmer John has noticed that the quality of milk given by his cows va

  • 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: 21826 Accepted: 7467 Description A musical melody is represented as a sequence of N (1<=N<=20000)notes that are integers in the ra

  • 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一

  • POJ 3261 Milk Patterns 求可重叠的 k 次最长重复子串(后缀数组)

    点击打开链接 Milk Patterns Time Limit: 5000MS Memory Limit: 65536K Total Submissions: 9361 Accepted: 4218 Case Time Limit: 2000MS Description Farmer John has noticed that the quality of milk given by his cows varies from day to day. On further investigatio

最新文章
  • Golang 还是 Rust?

    对C++不再有激情,服务器开发或者说后端,Golang还是Rust更有可能壮大起来? --cut-- lilydjwg在2016-05-09 15:20:49回答到: Go 和 Rust 的领域不太一样的.你的目标是什么? tonsonxu在2016-05-09 15:20:49回答到: 这一上来,就被move到程序员节点了... tonsonxu在2016-05-09 15:20:49回答到: @lilydjwg 目标是linux服务端高并发和内核引擎(偏算法).暂时还不想碰客户端.业务流程等

  • 在做 Flask app(或者其他类型的网站)集群的时候,需要自动将 Flask app 部署到一台新开的 Linux 服务器上。如何做比较好?直接上 Shell 脚本?还是用一些工具比如 Salt/Puppet/Ansible?

    RT. --cut-- freeznet在2016-05-10 20:35:58回答到: 安利docker~ happywowwow在2016-05-10 20:35:58回答到: fabric ? evlos在2016-05-10 20:35:58回答到: 我是来安利 Dokku 的 :D crazyxin1988在2016-05-10 20:35:58回答到: 密切关注- janxin在2016-05-10 20:35:58回答到: fabric或者docker hustlzp在2016-0

  • 出一套苹果 6 加未使用的全新配件

    国行iPhone 6 Plus的配件,包含小头充电器1个,lightning数据线1根,Earpods1个,全部全新未使用,塑封都在,218顺丰到付,淘宝二手担保交易,诚信交易. 联系方式,马化腾 242六零二四53九 --cut-- zhimingcc在2014-10-27 09:48:3回答到: 我也有一套国行的,感觉配件都不会怎么用....家里太多ios设备了 zjupigeon在2014-10-27 09:50:1回答到: 6能用么? visvi在2014-10-27 10:08:1回答

  • OPPO R7s显示CPU使用情况方法 OPPO R7s显示CPU使用情况方法

    OPPO R7s显示CPU使用情况方法.最近小编常在网上看到有网友留言说,想查看下手机CPU的使用情况,应该怎么查看呢,其实这个蛮简单的,下面就让小编就来教你们OPPO R7s显示CPU使用情况教程吧! 1)首先我们先打开[设置],然后找到[更多],打开再点击[开发者模式].(开发者模式在哪?)(如下图) 2)最后我们再把[显示CPU使用情况]那栏的开关打开即可.(如下图)

  • 年末工作助你防失眠 年末工作助你防失眠

    工作压力大失眠高发 随着社会的发展,都市生活节奏的加快,睡眠障碍已成为造成人类亚健康的头号难题. 在所有的睡眠障碍形式中,失眠是最常见的一种,其中又包括入睡困难.难以维持睡眠.睡眠程度浅.经常梦魇.早醒等.而医学上的"失眠"又可以根据时间长短分为三类:一是短暂性失眠,通常是持续几天;二是短期性失眠,通常持续两到三周;三是慢性失眠,持续时间为一个月以上. 而在年轻的白领群体当中,出现失眠症状的,律师.医生.记者.外企职员等人群发病率更高. 这些群体中的失眠现象,诱因通常有三种:主要原因是

  • 伤感旅途女生QQ空间flash模板动画_聆听陌生的歌曲,想起了熟悉的你

    FLASH动画模块使用方法: 1.登陆QQ空间→点击QQ空间上面的自定义. 2.点击新建模块→选择创建FLASH动画模块. 3.模块名称随便,用一个空格最好,FLASH地址上输入模块地址→更多设置随便→输入验证码 →确定保存.FLASH大小缩放比 例:1024*590,720*415,350*202 4.用鼠标调整一下FLASH的大小,自己想显示多大就拉多大. 5.最后点击保存,OK,添加完毕! Flash地址:http://www.popoho.com/flashload/fd.swf?id=

  • Win2003里面搭建视频服务器

    随着Internet和Intranet应用日益丰富,视频点播也逐渐应用于宽带网和局域网.人们已不再满足于浏览文字和图片,越来越多的人更喜欢在网上看电影.听音乐.而视频点播和音频点播功能的实现,则必须依靠流媒体服务技术.就目前来看,最流行的流媒体点播服务器只有两种,即Windows Media服务和Real Server.下面我们在这里主要讨论在Windows 2003 Server环境下如何搭建视频点播服务器.我们大家知道,Windows Media服务采用流媒体的方式来传输数据.通常格式的文件

  • 丁达尔现象详解 丁达尔现象详解

    丁达尔现象之一 当一束光线透过胶体,从入射光的垂直方向可以观察到胶体里出现的一条光亮的"通路",这种现象叫丁达尔现象,也叫丁达尔效应. 英国物理学家丁达尔(1820-1893年) ,首先发现和研究了胶体中的上述现象.这主要是胶体中分散质微粒散射出来的光. 丁达尔现象之二 1869年,英国科学家丁达尔发现了丁达尔现象. 光射到微粒上可以发生两种情况,一是当微粒直径大于入射光波长很多倍时,发生光的反射;二是微粒直径小于入射光的波长时,发生光的散射,散射出来的光称为乳光. 散射光的强度,随着

  • 乱斗西游罗刹经文怎么搭配 罗刹经文搭配分享 乱斗西游罗刹经文怎么搭配 罗刹经文搭配分享

    在乱斗西游这款游戏里,马上就要推出新的经文啦,那么原来的罗刹经文怎么样呢?罗刹经文的效果是什么样的呢?下面各位玩家们就和小编一起去看一下吧. 给各位玩家们分享一下乱斗西游里罗刹经文搭配方法及效果的想详细信息. 苦海经文 经文效果: 战阵内,己方英雄将提升(战阵内英雄法术强度之和)*x%的物理强度. 总结分析: 游戏中很多物法同存的英雄,比如禺狨王,二郎神,小白龙等等,这些英雄都是物理属性和法术属性相差不多的英雄,那么此次新推出的罗刹和无常经文就非常适合这类英雄 对目前队伍中双系混搭的英雄阵容会有

  • 索尼KDL-46EX720怎么样 索尼KDL-46EX720怎么样

    索尼KDL-46EX720的拖影现象基本没有,索尼的这款电视使用的Montionflow XR 200运动图像处理技术,图像特点有X-Reality 迅锐图像处理引擎,HD高清晰信号接收预,1080p HDMI输入,状态感应器.性能非常好. 主要参数 屏幕尺寸:46英寸 屏幕比例:16:9 屏幕分辨率:1920×1080 高清格式:1080p 背光性能:支持背光调节,LED背光源 建议观看距离:3.5米

热门推荐
  • 安全相册APP官方最新版下载 安全相册安卓版下载 安全相册APP官方最新版下载 安全相册安卓版下载 手机为你提供了随时拍照记录的便利,方便的同时你是否也希望这些图片能够安全的存放,当同事朋友 随手拿起你手机时,不至于让你提心吊胆.孩子要玩你手机的时候,不会问到让你尴尬的问题.这款专 门针对图片进行保密的软件,让你踏实安心,随时随地都能把手机借给好奇心强的人. 安全相册APP官方最新版下载 [亮点功能] 1.保护隐私,记录重要信息,钱包功能,可以存放密码.银行卡等重要信息,当遭遇入侵时,提供了数据自毁功能. 2.无限照片.视频隐藏 3.重构UI,清新简洁 4.钱包功能,非法闯入是提供自毁功能 5
  • 宋茜的名言 宋茜的名言 只要不抛弃不放弃,迟早会收获属于自己的蓝天. 夕阳无限好,只是近黄昏...不过一觉醒来,太阳又会美美的升起来. 虽然我不认识你们每个人,但是有你们的祝福就很开心了,你们是我最熟悉的''陌生人''.希望我会更努力,成为一个你们值得去爱和祝福的人. 你们说我是你们的正能量,其实,你们才是正能量的来源. 传言就是传言,传来传去,就成真事儿了-是真的,那你赚了!是假的,谁负责?
  • 外观革新 传苹果iPad5本月底正式发布 外观革新 传苹果iPad5本月底正式发布 依照惯例,苹果会在每年3月时发布一款新的iPad产品,就像当初发布iPad 2和iPad 3一样.不过在去年苹果公司发布iPad 4时,却稍稍偏离了这个传统的发布周期,比之前情况晚了一些.由此,近期坊间流传的消息称iPad 5将于本月末被发布,且这将是一次对iPad设计上的完全革新. 相信一个全新的9.7英寸iPad设计将会大受欢迎.就像当初iPad 2的推出一样,那时也是一次完全彻底的重新设计,不像其他版本的更新,外观并无大的变化,只是在屏幕分辨率.摄像头像素等上进行了提升. 近期来自多方的消
  • 四十亿年前火星大气氧含量远超地球 或曾存在生命 四十亿年前火星大气氧含量远超地球 或曾存在生命 这是2000年2月8日由中国南极考察队在南极格罗夫山地区发现的火星陨石,国际编号GRV 99027 据英国广播公司网站报道,一项最新研究显示,在大约40多亿年前,火星大气中的氧含量可能曾经相当丰富,这远比地球上进化出富氧大气的时间要早得多. 这正是最近一篇发表在科学杂志上的文章所要表达的中心思想.这篇文章对比了火星陨石中保存的火星古代纪录与今天自动探测器在火星上对岩石进行的分析之后得到了这一结论.英国牛津大学的巴纳德·伍德(Bernard Wood)博士认为这一结果与主流观点认为火星曾经是一颗温