tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

后缀数组的倍增算法


后缀数组的倍增算法

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.


推荐相关:

后缀数组的倍增算法

后缀数组的倍增算法_学科竞赛_高中教育_教育专区。后缀数组的倍增算法 后缀数组的倍增算法 var n,m,ans,st,en,i:longint; s:string; sa,rk,tsa,trk,h,sum...


后缀数组实现的倍增算法和DC3算法

后缀数组实现的倍增算法和DC3算法_计算机软件及应用_IT/计算机_专业资料。后缀数组实现的倍增算法和 DC3 算法 [cpp] view plaincopyprint? /*** 数据结后缀数组...


后缀数组的定义及实现

后缀数组的定义及实现_计算机软件及应用_IT/计算机_专业资料。后缀数组的定义,...现在假设 H 阶 段已经排序完成,即 Pos 数组,Rank 数组有正确的值,倍增算法的...


后缀数组笔记

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


统计一个字符串中不相同的回文子串数量的O(nlogn)算法

2.1 分段介绍 文献[1]介绍了用倍增算法和 DC3 算法求后缀数组的方法,时间复杂度为别为 O(nlogn) 和 O(n)。 文献[1]介绍了求 height 数组的方法,时间...


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

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


字符串ACM模板

(i,j); } 后缀数组 倍增算法 #include <stdio.h> #include <memory.h> #include <string.h> #include <algorithm> using namespace std; #define MAX ...


字符串算法模版

一些字符串算法模版 1、KMP 算法(敖教主整理的模版) /*注意:以下函数的数组...构造后缀树组的常用算法: 倍增算法: int wa[maxn],wb[maxn],wv[maxn],ws[...


分治和倍增

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


USACO题解(NOCOW整理版)

2.求出后缀数组 SA、名次数组 Rank (倍增法:O(nlogn) Dc3 算法:O(n)) 3.计算 height 数组并进行标准 RMQ 方法预处理(O(n)) 4.枚举 i,计算以 i 为...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com