当前位置:首页 >> 学科竞赛 >> 后缀数组的倍增算法

后缀数组的倍增算法


后缀数组的倍增算法

var n,m,ans,st,en,i:longint; s:string; sa,rk,tsa,trk,h,sum:array[1..10000] of longint; procedure suffix; var i,j,p:longint; begin m:=255; for i:=1 to n do begin trk[i]:=o

rd(s[i]); inc(sum[trk[i]]); end; for i:=2 to m do inc(sum[i],sum[i-1]); for i:=n downto 1 do begin sa[sum[trk[i]]]:=i; dec(sum[trk[i]]); end; rk[sa[1]]:=1; p:=1; for i:=2 to n do begin if trk[sa[i]]<>trk[sa[i-1]] then inc(p); rk[sa[i]]:=p; end; m:=p; j:=1; while m<n do begin move(rk,trk,sizeof(rk)); fillchar(sum,sizeof(sum),0); p:=0; for i:=n-j+1 to n do begin inc(p); tsa[p]:=i; end; for i:=1 to n do if sa[i]>j then

begin inc(p); tsa[p]:=sa[i]-j; end; for i:=1 to n do begin rk[i]:=trk[tsa[i]]; inc(sum[rk[i]]); end; for i:=2 to m do inc(sum[i],sum[i-1]); for i:=n downto 1 do begin sa[sum[rk[i]]]:=tsa[i]; dec(sum[rk[i]]); end; rk[sa[1]]:=1; p:=1; for i:=2 to n do begin if (trk[sa[i]]<>trk[sa[i-1]])or(trk[sa[i]+j]<>trk[sa[i-1]+j]) then inc(p); rk[sa[i]]:=p; end; m:=p; j:=j*2; end; h[1]:=0; p:=0; for i:=1 to n do begin if rk[i]=1 then continue; j:=sa[rk[i]-1]; while s[i+p]=s[j+p] do inc(p); h[rk[i]]:=p; if p>0 then dec(p); end; for i:=1 to n do begin for j:=sa[i] to n do write(s[j]); writeln; end;

end; begin readln(s); n:=length(s); suffix; for i:=1 to n do write(sa[i],' '); writeln; for i:=1 to n do write(h[i],' '); writeln; end.


更多相关文档:

后缀数组

【关键字】 字符串,后缀,后缀数组,名次数组,基数排序, 【正文】 一、后缀数组的实现 本节主要介绍后缀数组的两种实现方法:倍增算法(Doubling Algorithm)和 DC3 ...

快速轻量级后缀数组

在 接下来的论文里我们将会详细介绍这种快速轻量级构造后缀数组的算法。 关键词:后缀数组 倍增算法 诱导算法 递归算法 快速轻量级 ABSTRACT ABSTRACT We are not ...

后缀数组

Height 数组存储相邻两个 Sa 后缀之间公共前缀的长度,如图 处理后缀树组有两种算法:倍增、DC3 (我只会倍增,所以只写倍增。。。) 首先得搞懂基数排序:基数排序-...

后缀数组相关知识

构造后缀数组常用算法:倍增算法(NlogN) DC3 算法(N) 更加详细的,参见 WC2009 罗穗骞的论文。 整体算法流程: 预处理字符串中长度为 1 的字串 1、基数排序求出...

后缀数组笔记

OI 笔记]后缀数组学习笔记--后缀数组解题方法总结 2010-04-15 07:37 后缀数组...而 字符串中的其他字符都应该是大于 0 的(前面有提到,使用倍增算法前需要确保...

分治和倍增

分治和倍增 DJ(纯手打,复制请标明出处与作者,谢谢! ) 分治 ? 概念 ? 例题...很巧妙的算法。 3、后缀数组有的时候我们会碰到一些特殊的模型:在字符串中去掉...

第4部分 数据结构与算法提高班_图文

基于ST 表的RMQ 算法和树上倍增找LCA ? FFT、后缀数组等高级算法 4.3.2 倍增的两种情况 4.3.2.1 在变化规则相同的情况下加速状态转移 4.3.2.1.1 归并排序...

后缀数组题型讲解

后缀数组题型讲解_IT/计算机_专业资料 暂无评价|0人阅读|0次下载|举报文档 后缀数组题型讲解_IT/计算机_专业资料。ACM 能够用的上算法!!...

ACM算法目录整理V1.02

3.4 二分查找与三分查找 3.5 跳舞链 (1) 精确覆盖 (2)数独 4.字符串 //潘宣成 4.1 kmp 算法 4.2 AC 自动机 4.3 后缀数组 (1)倍增算法: (2) DC3...

算法练习题

NlogN^2 2-2 给定 N×NN\times NN×N 的二维数组 A,则在不改变数组的...(d*e+f)*g 转换为后缀表达式,当读入 f 时,堆栈里的内 容是什么(按堆栈...
更多相关标签:
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com