求height数组

时间:2021-07-19 01:02:01
  procedure getheight;
var
i,po1,po2:longint;
begin
for i:= to len do
begin
if k> then k:=k-;
po1:=i;po2:=sa[rank[i]-];
while (a[po1+k]=a[po2+k]) and (po1+k<=len) and (po2+k<=len) do
inc(k);
height[i]:=k;
end;
end;

其中height[i]表示suffix(i)与suffix(sa[rank[i]-1])的最长公共前缀

____________________________________________________

c++

void getheight(){
int k=;
int po1,po2;
for (int i=;i<=n;i++){
po1=i,po2=sa[rank[i]-];
if (k) k--;
while ((st[po1+k]==st[po2+k])&&(po1+k<=len)&&(po2+k<=len))
k++;
height[rank[i]-]=k;
}
}

其中height[i]表示rank[i]+1与rank[i]的最长公共前缀

求height数组的更多相关文章

  1. 【POJ2774】Long Long Message(后缀数组求Height数组)

    点此看题面 大致题意: 求两个字符串中最长公共子串的长度. 关于后缀数组 关于\(Height\)数组的概念以及如何用后缀数组求\(Height\)数组详见这篇博客:后缀数组入门(二)--Height ...

  2. Java后缀数组-求sa数组

    后缀数组的一些基本概念请自行百度,简单来说后缀数组就是一个字符串所有后缀大小排序后的一个集合,然后我们根据后缀数组的一些性质就可以实现各种需求. public class MySuffixArrayT ...

  3. 后缀数组入门(二)——Height数组与LCP

    前言 看这篇博客前,先去了解一下后缀数组的基本操作吧:后缀数组入门(一)--后缀排序. 这篇博客的内容,主要建立于后缀排序的基础之上,进一步研究一个\(Height\)数组以及如何求\(LCP\). ...

  4. 关于后缀数组的倍增算法和height数组

    自己看着大牛的论文学了一下后缀数组,看了好久好久,想了好久好久才懂了一点点皮毛TAT 然后就去刷传说中的后缀数组神题,poj3693是进化版的,需要那个相同情况下字典序最小,搞这个搞了超久的说. 先简 ...

  5. 后缀数组的一些性质----height数组

    height数组:定义 height[i] = suffix[i-1] 和 suffix[i] 的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀.那么对于 j 和 k 不妨设 Rank[j] & ...

  6. 【后缀数组之height数组】

    模板奉上 int rank[maxn],height[maxn]; void calheight(int *r,int *sa,int n) { ; ;i<=n;i++) rank[sa[i]] ...

  7. 求出数组中所有数字的和&amp&semi;&amp&semi;弹出层效果

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...

  8. BZOJ2251 &lbrack;2010Beijing Wc&rsqb;外星联络 后缀数组 &plus; Height数组

    Code: #include <bits/stdc++.h> #define setIO(s) freopen(s".in", "r", stdin ...

  9. 洛谷P2408 不同子串个数 后缀数组 &plus; Height数组

    ## 题目描述: 给你一个长为 $N$ $(N<=10^5)$ 的字符串,求不同的子串的个数我们定义两个子串不同,当且仅当有这两个子串长度不一样 或者长度一样且有任意一位不一样.子串的定义:原字 ...

随机推荐

  1. HTML入门教程

    什么是 HTML?     HTML(Hyper Text Markup Language)超文本标记语言,是用来描述网页的一种语言,不是一种编程语言,而是一种标记语言 (markup languag ...

  2. 链接后加&quot&semi;&sol;&quot&semi;与不加&quot&semi;&sol;&quot&semi;的区别

    1.http://www.abc.com/abc2.http://www.abc.com/abc/ 当Web服务器接收到对某个末尾不含斜杠的url请求时,例如“http://www.abc.com/a ...

  3. atitit&period; 浏览器插件 控件 applet 的部署,签名总结 浏览器 插件 控件 的签名安全机制o9o

    atitit. 浏览器插件 控件   applet 的部署,签名总结 浏览器 插件 控件 的签名安全机制o9o 1. 服务器部署签名 1 2. 签名流程::生成密钥..导出cert正书,签名 1 3. ...

  4. vector&comma;arraylist&comma; linkedlist的区别是什么

    LinkedList类 LinkedList实现了List接口,允许null元素. 此外LinkedList提供额外的get,remove,insert方法在LinkedList的首部或尾部. Lin ...

  5. magento数据添加

    1.第一种方法是一个字段一个字段地添加! $record = Mage::getModel('warehouse/record');      $record->addData($postDat ...

  6. ajaxFileUpload上传文件简单示例

    写在前面: 上传文件的方式有很多,最近在做项目的时候,一开始也试用了利用jquery的插件ajaxFileUpload来上传大文件,下面,用一个上传文件的简单例子,记录下,学习的过程~~~ 还是老样子 ...

  7. BZOJ&period;4241&period;历史研究&lpar;回滚莫队 分块&rpar;

    题目链接 \(Description\) 长度为n的数列,m次询问,每次询问一段区间最大的 \(A_i*tm_i\) (重要度*出现次数) \(Solution\) 好像可以用莫队做,但是取max的操 ...

  8. Nexus 使用配置

    Nexus使用的一些基本设置 1.更改*仓库地址为私服地址 既然我们配置了私服,那么相应的,我们的项目就应该使用Nexus的地址(Public Repository)来下载jar包 1.1.基于PO ...

  9. flex自适应宽度显示省略号

    text-overflow:ellipsis文本溢出显示省略号,一般的搭配用法如下: div{ text-overflow:ellipsis; overflow:hidden; white-space ...

  10. Webpack笔记(三)——一款破产版脚手架的开发

    前些天一直在学习入门Webpack,后来尝试了自己搭建一下一个简单的React开发环境,后来就在想可不可以自己写一个简单的脚手架,以免每次搭建一个简单的开发环境都需要自己一个个的配置,这样很麻烦,使用 ...