大数据培训新三板挂牌机构 股票代码:837906 | EN CN
Java是什么?
Java历史
Java语言特点
C++ VS Java比较
Java工厂设计模式
Java抽象工厂模式
Java单例模式
Java建造者(Builder)模式
Java原型模式
Java适配器模式
Java桥接模式
Java获取网络文件大小
Java套接字到单一的客户端
Java连接套接字
Java URL部分
Java URL连接日期
Java下载网页
Java主机指定IP地址
Java确定本地IP地址
Java检查端口占用
Java查找代理服务器设置
Java创建Socket
Java线程实例
Java检查线程活着
Java如何检查一个线程停止或没有?
Java解决死锁实例
Java如何获取正在运行的线程的优先级?
Java如何监视线程的状态?
Java获取线程名称
Java线程生产者消费者问题
Java如何设置线程的优先级?
Java如何停止线程一会儿?
Java如何暂停线程?
Java获取线程ID
Java如何检查线程的优先级?
Java显示所有正在运行的线程?
Java显示线程状态
Java中断一个线程
Java Applet实例
Java创建Applet
Java使用Applet创建横幅
Java使用Applet显示时钟?
Java在一个Applet创建不同形状
Java如何使用Applet填充形状的颜色?
Java使用Applet跳转到一个链接
Java在Applet创建事件监听器
Java使用Applet显示图像
Java使用Applet在新窗口中打开链接
Java使用Applet播放声音?
Java使用Applet读取文件
Java使用Applet写入文件
Java中Swing应用程序applet
Java简单的图形用户界面-GUI
Java以不同的字体显示文本
Java使用GUI画一条线
Java创建框架-frame
Java使用GUI显示多边形
Java在矩形中显示文本
Java GUI显示不同形状
Java如何绘制GUI实心矩形?
Java创建GUI透明光标
Java检查GUI平滑处理状态
Java在框架中显示颜色
Java GUI显示饼图
Java使用图形用户界面绘制文本
Java编辑表-table
Java 使用prepared语句
Java使用保存点和回滚
Java同时执行数据库多个SQL命令
Java使用行方法
Java使用列方法
Java正则表达式实例
Java将字符串分割
Java搜索重复单词
Java查找出现的单词
Java最后一个词的索引
Java模式匹配
Java删除空格
Java匹配电话号码
Java计数组词
Java搜索词组
Java拆分正则表达式
Java替换第一个出现字符串
Java检查日期格式
Java验证电子邮件地址格式
Java替换所有匹配字符串
Java使每个单词的第一个字母大写
从XML创建SqlSessionFactory实例
不使用XML来创建SqlSessionFactory
从SqlSessionFactory获取SqlSession
映射SQL语句
作用域和生命周期
Mapper XML配置
properties元素
Settings元素
typeAliases 元素
typeHandlers元素
理解CacheLine与写出更好的JAVA
Java核心技术点之动态代理
更好的使用JAVA线程池
理解Java中字符流与字节流的区别
深入分析Java方法反射的实现原理
关于Java面试,你应该准备这些知识点
Java内存模型
2017年你不能错过的Java类库
Leakcanary Square的一款Android/Java内存泄漏检测工具
Java Synchronised机制
Java核心技术点之注解
JVM(8):JVM知识点总览-高级Java工程师面试必备
JVM(3):Java GC算法 垃圾收集器
JVM(1):Java 类的加载机制
解决ActiveMQ中,Java与C++交互中文乱码问题
关于Java Collections的几个常见问题
Java I/O 总结
JVM源码分析之Java对象的创建过程
JVM源码分析之Java类的加载过程
Java GC的那些事(下)
Java GC的那些事(上)
java对象头的HotSpot实现分析
面试的角度诠释Java工程师(一)
面试的角度诠释Java工程师(二)
框架开发之Java注解的妙用
谈谈Java反射机制
Java并发:volatile内存可见性和指令重排
死磕Java并发:Java内存模型之happens-before
死磕Java并发:深入分析volatile的实现原理
死磕Java并发:深入分析synchronized的实现原理
Java 10 可能对 Lambda 表达式进行升级
G1垃圾回收器中的字符串去重(Java 8 Update 20)
Java RESTful框架的性能比较
理解RxJava的线程模型
继续了解Java的纤程库 – Quasar
Java中的纤程库 – Quasar
Java豆瓣电影爬虫——抓取电影详情和电影短评数据
Java集合框架源码剖析:LinkedHashSet 和 LinkedHashMap
Java Lambda表达式初探
Java中的陷阱题
Java 9的这一基本功能,你可能从未听过
关于Java并发编程的总结和思考
几种简单的负载均衡算法及其Java代码实现
JAVA虚拟机关闭钩子(Shutdown Hook)
Java 脚本化编程指南
Java Scripting API 使用示例
Java 8 的 Nashorn 脚本引擎教程
如何开始使用 Java 机器学习
CognitiveJ —— Java 的图像分析库
Java 性能优化的五大技巧
Java 解惑:Comparable 和 Comparator 的区别
Google Java编程风格指南
java NIO详解
Java 异常处理的误区和经验总结
Java语法糖(4):内部类
Java语法糖(3):泛型
Java语法糖(2):自动装箱和自动拆箱
Java消息队列任务的平滑关闭
Java语法糖(1):可变长度参数以及foreach循环原理
2016最流行的Java EE服务器
自己写一个java.lang.reflect.Proxy代理的实现
java 如何在pdf中生成表格
如何防止单例模式被JAVA反射攻击
java虚拟机 jvm 局部变量表实战
聊聊并发-Java中的Copy-On-Write容器
java.lang.Instrument 代理Agent使用
Java开发者需要了解的移动开发编程语言
13个不容错过的Java项目
2016年7款最佳 Java 框架推荐
Java 开发者值得关注的 11 个技术博客
Redmonk发布Java框架流行度调研结果
Java 8开发的4大顶级技巧
GitHub漫游指南:10个值得你关注的Java项目
除了Guava,Java开发者还值得了解的5个谷歌类库
Java中创建对象的5种不同方法
Java性能优化全攻略
奇怪的Java题:为什么1000 == 1000返回为False,而100 == 100会返回为True?
11个最值得Java开发者收藏的网站
Java的常见误区与细节
对Java意义重大的7个性能指标
Java调优经验谈
关于Java并发编程的总结和思考
HDFS Federation设计动机与基本原理
《Effective STL》学习笔记(第三部分)
《Effective STL》学习笔记(第二部分)
《Effective STL》学习笔记(第一部分)
数据结构之位图
Thrift使用指南
Cassandra概要介绍
Cassandra部署与安装
Cassandra客户端
Cassandra数据模型
Cassandra中的各种策略
数据结构之树状数组
数据结构之伸展树
数据结构之后缀数组
数据结构之堆
浅析MRv1与MRv2的API兼容性
Apache Tez最新进展
运行在YARN上的计算框架
从传统操作系统角度理解Hadoop YARN

数据结构之后缀数组

于2017-03-26由小牛君创建

分享到:



1. 概述

后缀数组是一种解决字符串问题的有力工具。相比于后缀树,它更易于实现且占用内存更少。在实际应用中,后缀数组经常用于解决字符串有关的复杂问题。

本文大部分内容摘自参考资料[1][2]。

2. 后缀数组

2.1   几个概念

(1)后缀数组SA 是一个一维数组,它保存1..n 的某个排列SA[1],SA[2],……,SA[n],并且保证Suffix(SA[i]) < Suffix(SA[i+1]),1≤i<n。也就是将S 的n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。其中,suffix(i)表示字符串s[i,i+1…n-1],即字符串s起始于第i个字符的后缀。

(2)名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。

简单的说,后缀数组是“排第几的是谁?”,名次数组是“你排第几?”。容易看出,后缀数组和名次数组为互逆运算。

(3)height 数组:定义height[i]=suffix(SA[i-1])和suffix(SA[i])的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。

(4) h[i]=height[rank[i]],也就是suffix(i)和在它前一名的后缀的最长公共前缀。

(5)LCP(i,j):对正整数i,j 定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]),其中i,j 均为1 至n 的整数。LCP(i,j)也就是后缀数组中第i 个和第j 个后缀的最长公共前缀的长度。其中,函数lcp(u,v)=max{i|u=v},也就是从头开始顺次比较u 和v 的对应字符,对应字符持续相等的最大位置,称为这两个字符串的最长公共前缀。

2.2   几个性质

(1)LCP(i,j)=min{height[k]|i+1≤k≤j},也就是说,计算LCP(i,j)等同于询问一维数组height 中下标在i+1 到j 范围内的所有元素的最小值。

证明略。

(2)对于i>1 且Rank[i]>1,一定有h[i]≥h[i-1]-1。

证明:设suffix(k)是排在suffix(i-1)前一名的后缀,则它们的最长公共前缀是h[i-1]。那么suffix(k+1)将排在suffix(i)的前面(这里要求h[i-1]>1,如果h[i-1]≤1,原式显然成立)并且suffix(k+1)和suffix(i)的最长公共前缀是h[i-1]-1,所以suffix(i)和在它前一名的后缀的最长公共前缀至少是h[i-1]-1。按照h[1],h[2],……,h[n]的顺序计算,并利用h 数组的性质,时间复杂度可以降为O(n)。

3. 后缀数组实现

本节给出高效计算SA,Rank,height和h的算法

(1) 计算名次数组Rank与后缀数组SA

采用倍增算法,先求出名次Rank,然后在O(n)时间内求得后缀数组SA。用倍增的方法对每个字符开始的长度为2^k 的子字符串进行排序,求出排名,即rank 值。k 从0 开始,每次加1,当2k 大于n 以后,每个字符开始的长度为2^k 的子字符串便相当于所有的后缀。并且这些子字符串都一定已经比较出大小,即rank 值中没有相同的值,那么此时的rank 值就是最后的结果。每一次排序都利用上次长度为2^(k-1) 的字符串的rank 值,那么长度为2^k 的字符串就可以用两个长度为2^(k-1) 的字符串的排名作为关键字表示,然后进行基数排序,便得出了长度为2k 的字符串的rank 值。以字符串“aabaaaab”为例,整个过程如下图所示。其中x、y 是表示长度为2k 的字符串的两个关键字。

(2) 计算数组h

可以令i从1 循环到n按照如下方法依次算出h[i]:

若 Rank[i]=1,则h[i]=0。字符比较次数为0。

若 i=1 或者h[i-1]≤1,则直接将Suffix(i)和Suffix(Rank[i]-1)从第一个字符开始依次比较直到有字符不相同,由此计算出h[i]。字符比较次数为h[i]+1,不超过h[i]-h[i-1]+2。

否则,说明i>1,Rank[i]>1,h[i-1]>1,根据性质2,Suffix(i)和Suffix(Rank[i]-1)至少有前h[i-1]-1 个字符是相同的,于是字符比较可以从h[i-1]开始,直到某个字符不相同,由此计算出h[i]。字符比较次数为h[i]-h[i-1]+2。

可求得最后算法复杂度为O(n)。

4. 后缀数组应用

4.1 单个字符串相关问题

(1) 可重叠最长重复子串。给定一个字符串,求最长重复子串,这两个子串可以重叠。

『解析』只需要求height 数组里的最大值即可。

(2) 不可重叠最长重复子串。给定一个字符串,求最长重复子串,这两个子串不能重叠。

『解析』先二分答案,把题目变成判定性问题:判断是否存在两个长度为k 的子串是相同的,且不重叠。解决这个问题的关键还是利用height 数组。把排序后的后缀分成若干组,其中每组的后缀之间的height 值都不小于k。例如,字符串为“aabaaaab”,当k=2 时,后缀分成了4 组:

容易看出,有希望成为最长公共前缀不小于k 的两个后缀一定在同一组。然后对于每组后缀,只须判断每个后缀的sa 值的最大值和最小值之差是否不小于k。如果有一组满足,则说明存在,否则不存在。整个做法的时间复杂度为O(nlogn)。

(3) 可重叠的k 次最长重复子串。给定一个字符串,求至少出现k 次的最长重复子串,这k 个子串可以重叠。

『解析』 先二分答案,然后将后缀分成若干组。不同的是,这里要判断的是有没有一个组的后缀个数不小于k。如果有,那么存在k 个相同的子串满足条件,否则不存在。这个做法的时间复杂度为O(nlogn)。

(4) 最长回文子串。给定一个字符串,求最长回文子串。

『解析』 将整个字符串反过来写在原字符串后面,中间用一个特殊的字符隔开。这样就把问题变为了求这个新的字符串的某两个后缀的最长公共前缀。

(5) 连续重复子串。给定一个字符串L,已知这个字符串是由某个字符串S 重复R 次而得到的,求R 的最大值。

『解析』穷举字符串S 的长度k,然后判断是否满足。判断的时候,先看字符串L 的长度能否被k 整除,再看suffix(1)和suffix(k+1)的最长公共前缀是否等于n-k。在询问最长公共前缀的时候,suffix(1)是固定的,所以RMQ问题没有必要做所有的预处理, 只需求出height 数组中的每一个数到height[rank[1]]之间的最小值即可。整个做法的时间复杂度为O(n)。

(6) 重复次数最多的连续重复子串。给定一个字符串,求重复次数最多的连续重复子串。

『解析』先穷举长度L,然后求长度为L 的子串最多能连续出现几次。首先连续出现1 次是肯定可以的,所以这里只考虑至少2 次的情况。假设在原字符串中连续出现2 次,记这个子字符串为S,那么S 肯定包括了字符r[0], r[L], r[L*2],r[L*3], ……中的某相邻的两个。所以只须看字符r[L*i]和r[L*(i+1)]往前和往后各能匹配到多远,记这个总长度为K,那么这里连续出现了K/L+1 次。最后看最大值是多少。

穷举长度L 的时间是n,每次计算的时间是n/L。所以整个做法的时间复杂度是O(n/1+n/2+n/3+……+n/n)=O(nlogn)。

4.2 两个字符串相关问题

(1) 最长公共子串。给定两个字符串A 和B,求最长公共子串。

『解析』先将第二个字符串写在第一个字符串后面,中间用一个没有出现过的字符隔开,再求这个新的字符串的后缀数组。当suffix(sa[i-1]) 和suffix(sa[i])不是同一个字符串中的两个后缀时,max{height[i]}才是满足条件

(2) 长度不小于k 的公共子串的个数。给定两个字符串A 和B,求长度不小于k 的公共子串的个数(可以相同)。

『解析』基本思路是计算A 的所有后缀和B 的所有后缀之间的最长公共前缀的长度,把最长公共前缀长度不小于k 的部分全部加起来。先将两个字符串连起来,中间用一个没有出现过的字符隔开。按height 值分组后,接下来的工作便是快速的统计每组中后缀之间的最长公共前缀之和。扫描一遍,每遇到一个B 的后缀就统计与前面的A 的后缀能产生多少个长度不小于k 的公共子串,这里A 的后缀需要用一个单调的栈来高效的维护。然后对A 也这样做一次。

4.3 多个字符串相关问题

(1) 不小于k 个字符串中的最长子串。给定n 个字符串,求出现在不小于k 个字符串中的最长子串。

『解析』将n 个字符串连起来,中间用不相同的且没有出现在字符串中的字符隔开,求后缀数组。然后二分答案:将后缀分成若干组,判断每组的后缀是否出现在不小于k 个的原串中。这个做法的时间复杂度为O(nlogn)。

(2) 每个字符串至少出现两次且不重叠的最长子串。给定n 个字符串,求在每个字符串中至少出现两次且不重叠的最长子串。

『解析』做法和上题大同小异,也是先将n 个字符串连起来,中间用不相同的且没有出现在字符串中的字符隔开,求后缀数组。然后二分答案,再将后缀分组。判断的时候,要看是否有一组后缀在每个原来的字符串中至少出现两次,并且在每个原来的字符串中,后缀的起始位置的最大值与最小值之差是否不小于当前答案(判断能否做到不重叠,如果题目中没有不重叠的要求,那么不用做此判断)。这个做法的时间复杂度为O(nlogn)。

(3) 出现或反转后出现在每个字符串中的最长子串。给定n 个字符串,求出现或反转后出现在每个字符串中的最长子串。

『解析』这题不同的地方在于要判断是否在反转后的字符串中出现。其实这并没有加大题目的难度。只需要先将每个字符串都反过来写一遍,中间用一个互不相同的且没有出现在字符串中的字符隔开,再将n 个字符串全部连起来,中间也是用一个互不相同的且没有出现在字符串中的字符隔开,求后缀数组。然后二分答案,再将后缀分组。判断的时候,要看是否有一组后缀在每个原来的字符串或反转后的字符串中出现。这个做法的时间复杂度为O(nlogn)。

5. 总结

后缀数组实际上可以看作后缀树的所有叶结点按照从左到右的次序排列放入数组中形成的,所以后缀数组的用途不可能超出后缀树的范围。甚至可以说,如果不配合LCP,后缀数组的应用范围是很狭窄的。但是LCP 函数配合下的后缀数组就非常强大,可以完成大多数后缀树所能完成的任务,因为LCP 函数实际上给出了任意两个叶子结点的最近公共祖先,这方面的内容大家可以自行研究。

6. 参考资料

(1) 许智磊,IOI2004 国家集训队论文《后缀数组》

(2) 罗穗骞,IOI2004 国家集训队论文《后缀数组—处理字符串的有力工具》

----------------------------------------------------------------------------------------------
更多关于数据结构和算法的介绍,请查看:数据结构与算法汇总
----------------------------------------------------------------------------------------------