没有合适的资源？快使用搜索试试~ 我知道了~

文库首页课程资源C/C++后缀数组--许智磊

后缀数组--许智磊

后缀数组

5星 · 超过95%的资源需积分: 21 23 下载量 133 浏览量 2013-03-12 21:36:50 上传评论收藏 764KB PPT 举报

温馨提示

试读

34页

后缀数组--许智磊

资源推荐

资源详情

资源评论

后缀数组

芜湖一中　许智磊

后缀数组——字符串处理中的有力武器

后缀树的一个简单而高效的替代品

当今字符串处理研究中的热门

让我们一同揭开她神秘的面纱

后缀数组——定义和符号

字符集、字符、字符串都按照惯常的定义

字符串 S 的长度表示为 len(S)

字符串的下标从 1 开始到 len(S) 结束

字符串 S 的第 i 个字符表示为 S[i]

从 i 到 j 这一段的子串表示为 S[i..j]

后缀是一种特殊的子串

从某个位置 i 开始到整个串的末尾结束

S 的从 i 开头的后缀等价于 S[i..len(S)]

后缀数组——定义和符号

约定一个字符集 Σ

待处理的字符串约定为 S ，约定 len(S)=n

规定 S 以字符“ $” 结尾，即 S[n]=“$”

“$” 小于 Σ 中所有的字符

除了 S[n]=“$” 之外， S 的其他字符都属于 Σ

对于约定的字符串 S ，其 i 开头的后缀表示为

Suffix(i)

后缀数组——定义和符号

字符串的大小关系　按照通常所说的“字典顺序”进行比较

我们对 S 的 n 个后缀按照字典顺序从小到大排序

将排序后的后缀的开头位置顺次放入数组 SA 中，称为

后缀数组

令 Rank[i] 保存 Suffix(i) 在排序中的名次，称数组 Rank 为

名次数组

后缀数组——构造方法

把 n 个后缀当作 n 个字符串，按照普通的方法进行排

序 —— O(n

)

低效的原因 —— 把后缀仅仅当作普通的、独立

的字符串，忽略了后缀之间存在的有机联系。

如何构造后缀数组 ?

剩余33页未读，继续阅读

评论收藏

内容反馈

资源评论

资源反馈

评论星级较低，若资源使用遇到问题可联系上传者，3个工作日内问题未解决可申请退款~

JW_7066

2018-05-02

资源不错！
hugett

2014-04-12

很好的资料

luyuncheng

粉丝: 82
资源: 28

上传资源快速赚钱

我的内容管理展开

我的资源快来上传第一个资源

我的收益

登录查看自己的收益

我的积分登录查看自己的积分

我的C币登录后查看C币余额

我的收藏

我的下载

下载帮助

前往需求广场，查看用户热搜

后缀数组--许智磊

许智磊关于后缀数组的PDF文件

后缀数组1

后缀数组与应用

罗穗骞《后缀数组——处理字符串的有力工具》(有算法源码和解题源码)

MF算法 --- 传说后缀数组中最快的构建法

后缀数组(Suffix Array)

2014-许智磊-后缀数组1

后缀数组资料打包（论文+PPT+笔记）

后缀数组PPT详细解答

ACM 2004年国家集训队论文

IOI国家集训队论文集1999-2019

IOI国家集训队2004论文集

acm国家集训队2004年论文合集

Qt上位机软件串口通讯，视频源码，免费下载

张玉生《C语言程序设计》双色版 C语言程序设计理论教材习题参考答案.pdf

代码随想录算法PDF.rar

qt-everywhere-src-5.12.12源码

Qt Qss三套样式文件 qss.zip

C++读取excel数据

第十二届蓝桥杯大赛模拟赛（第三期）.pdf

通俗易懂的校园导航系统

2021csp-j初赛试题及答案.docx

C++语言程序设计第五版郑莉

基于STM32F103+ADS1292的心率实时显示（串口助手），心电图波形

Halcon实战视频教程，超人视觉，初级和高级版视频，无密码高清

STM32F103开发的无刷直流电机控制FOC

【C++】开发软件资料集.zip

Visual Studio 2019 安装包vs_community__174506433.1587653313.zip

最新资源