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

后缀数组之最长公共前缀

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

最新文章
  • dns 服务器性能

    双 Intel Xeon E5 2650 v2 192 GB 内存 3x 500 SSD RAID0 这样一台权威服务器powerdns每秒可以处理多少次dns查询请求 --cut-- acpp在2015-05-06 17:11:1回答到: 看程序员的编码能力.. holinhot在2015-05-06 17:35:4回答到: @acpp powerdns不是现成的吗 holinhot在2015-05-06 17:55:4回答到: 试了下linode 最便宜的配置 queryperf -d te

  • 烂架构的代码是如何最后变好的呢。

    不知道大家有没有这样的经历,你当前所做的项目的代码很乱,无架构可言,每天又会有源源不断的新需求过来,参与开发的人并不全是比较牛的人,所以还会补充进去一些烂代码.这样的代码最后如何能变好,或者怎么做才能让这样的代码变得更好.人很少,需求很多,代码比较烂. --cut-- YouXia在2016-05-09 04:40:10回答到: 重构 hh3755在2016-05-09 04:40:10回答到: @YouXia 人少,需求多.是要抽出一个人来做专门重构吗.如何解决项目进度和重构本身挤占时间的冲突

  • 成语春诵夏弦的故事

    成语春诵夏弦的故事 成语发音:chūn sòng xià xián 成语解释:指应按季节采取不同的学习方式.后泛指读书学习 成语出处:西汉 戴圣<礼记 文王世子>:"春诵夏弦,大师诏之." 成语繁体:萅誦夏絃 感情色彩:中性成语 成语用法:联合式;作谓语;泛指读书学习 成语结构:联合式成语 产生年代:古代成语 成语例句:入于门墙,如造阙里.春诵夏弦,载飏淑声.(唐 刘禹锡<许州文宣王新庙碑>)

  • 《射雕ZERO》自由操控·够酷拽 《射雕ZERO》自由操控·够酷拽

    六大自由 自由操控·够酷拽 自由动作·够痛快 自由社交·没距离 自由生涯·够自在 自由挑战·没规矩 自由职业·没界限 自由操控·够酷拽[多设备多模式操控体验] <射雕ZERO>使用头戴设备.手柄.键鼠皆可顺畅体验,超前的头戴设备可带来更具临场感的画面感受,接口深度开发让手柄支持更全面.更有传统动作.ZERO原创.经典角色扮演等多种操作模式确保上手无忧!

  • 手Q公众号:会像微信一样火吗? 手Q公众号:会像微信一样火吗?

    前天手Q公众号限量注册,根据手Q公众号官方公开的数据是在1.5秒内抢被抢完,一共有11万人参与了此次注册申请.为何会吸引这么多人的目光?就是因为大多数人都抱着一个思想,在第一时间注册能享受到红利期,特别是经历过微信公众平台的人,更能体会. 为何微信公众平台有红利期,手Q不一定有 但毕竟手Q公众平台毕竟不是微信公众平台,真正有想象中的红利期吗? 1:很多有资源的不看好微信,从而竞争小.而手Q一开始竞争就激烈 我是微信公众平台推出的第三天就注册的,确实第一时间做微信公众平台的草根可以说都享受到了红利

  • 正则表达式速查表(ASP.NET)

    出处:RegExLib.com Regular Expression Cheat Sheet (.NET) 元字符 说明 ^ 匹配字符串的开始位置 $ 匹配字符串的结束位置 . 匹配任意单个字符(换行符 \n 除外) | 交替 {-} 指定要限定的数量 [...] 指定要匹配的字符集 (-) 对表达式进行逻辑分组 * 匹配零或多个前面的表达式 + 匹配一或多个前面的表达式 ? 匹配零或一个前面的表达式 \ 放在上面任何一个字符之前,表示匹配该字符本身.放在其他特殊字符后面,表示字符转义(见下面)

  • JavaScript 库

    JavaScript 库 - jQuery.Prototype.MooTools. JavaScript 框架(库) JavaScript 高级程序设计(特别是对浏览器差异的复杂处理),通常很困难也很耗时. 为了应对这些调整,许多的 JavaScript (helper) 库应运而生. 这些 JavaScript 库常被称为 JavaScript 框架. 在本教程中,我们将了解到一些广受欢迎的 JavaScript 框架: jQuery Prototype MooTools 所有这些框架都提供针

  • 关于物流企业营业管理信息化建设的研究

    关于物流企业运营管理信息化建设的研究 [摘 要]:本文围绕物流企业运营管理信息化建设问题,分析了传统物流企业信息化的必然趋势.现状及其重要意义,并通过对信息技术提升物流企业管理水平的研究,提出了物流企业运营管理信息系统基本框架模式. [关键词]:信息系统 电子商务 物流 板块 EDI 一.前言 进入21世纪,在由生产.流通.消费组成的经济社会中,流通领域(由物流.商流.信息流.资金流四部分组成)将起到愈来愈大的作用,特别是物流产业的发展有可能代替商流成为经济发展的龙头,因为没有比物流更能消除生产

  • EJB3.0实业bean

    EJB3.0实体bean 6.5 持久化实体管理器EntityManager EntityManager 是用来对实体Bean进行操作的辅助类.他可以用来产生/删除持久化的实体Bean,通过主键查找 实体bean,也可以通过EJB3 QL语言查找满足条件的实体Bean.EntityManager 的获取前面已经介绍过,可以通 [email protected],例: @PersistenceContext(unitName="foshanshop") EntityManager em;

  • 一个算法求解,该如何解决

    一个算法求解, Suppose we have a rod of n inches to sell. You may sell it without cutting, or you may cut it into several pieces to sell. If you cut it, every piece must be a multiple of inches. The price of each piece depends on its length, but may not be

热门推荐
  • “将游戏产业版图延伸十倍”女人何敢出此豪言 “将游戏产业版图延伸十倍”女人何敢出此豪言 女人,在传统的定义中,是温婉.内敛.体贴的贤妻良母形象,而现在时代不同了,男女平等.机会平等,英雄不问出处,也不再拘泥于性别,近年有非常多优秀的女性高管.创业者涌现出来.日前,一家希望"将金融与电商嵌入游戏"的企业进入公众视线,其创始人霸气地想要把目前已保持高速发展拥有17年历史年产值近千亿的游戏市场扩大到万亿规模,这个女人就是米谷科技CEO--吴丹枫. 吴丹枫,前支付宝游戏行业掌门人.熟悉吴丹枫的人常用工作狂.江湖 (预订)味.雷厉风行.完美主义等词汇来形容她.这个女人,曾经在不到5
  • 作业互助组离线状态总是联网失败怎么办 作业互助组离线状态总是联网失败怎么办 作业互助组离线状态总是联网失败怎么办 原因一:网络问题,请检查网络. 原因二:作业互助组版本过久问题才会导致联网失败,请检查更新最新版本软件. 原因三:作业互助组app与手机系统不兼容,请更换手机系统尝试一下. 原因四:作业互助组app新版本故障所以导致总是提示离线状态,卸载应用再重装. 原因五:咨询官方客服等待解决.
  • 水电改造工程图有什么作用 水电改造工程图有什么作用 作为家装水电改造的注意事项之一,就是在工程完工之后,一定要向装修公司索要水电改造工程图,或者说是水电改造的施工图.因此,有朋友会问:水电改造工程图有什么作用?的确,水电改造工程图有着相当重要的作用. 以上是一份水电改造工程的施工图.透过这份水电改造工程施工图,我们可以了解到相当多的信息.从中也可知说水电改造工程施工图的重要性. 一.水电改造施工图,是水电改造的施工依据 水电改造施工图,是依据水电改造规划制定的,用以指导水电改造施工的开展.因此,在水电改造工程中,这份图纸可以说是必不可少的. 二.