笔试算法题(40):后缀数组 & 后缀树(Suffix Array & Suffix Tree)
议题:后缀数组(Suffix Array)
分析:
后缀树和后缀数组都是处理字符串的有效工具,前者较为常见,但后者更容易编程实现,空间耗用更少;后缀数组可用于解决最长公共子串问题,多模式匹配问题,最长回文串问题,全文搜索等问题;
后缀数组的基本元素:
给定一个string,其长度为L,后缀指的是从string的某一个位置i(0<=i<L)开始到串末尾(string[L-1])的一个子串,表示为suffix(i);
L个suffix(i)按照字典顺序排列并顺序存储在一个数组SA[L]中,则SA[L]称为后缀数组,其元素值存储的是suffix(i)的起始字符在string中的位置;
每一个suffix[i]对应在SA[k]数组中的一个位置,将这个对应的位置存储为Rank[i],时间复杂度为O(N);对于任意两个 suffix[i]和suffix[j],由于知晓其在Rank[L]中的前后位置,所以在O(1)的时间内就可以得出他们的字典序大小关系;
构建SA[i]数组中相邻元素的最长公共前缀(LCP,Longest Common Prefix),Height[i]表示SA[i]和SA[i-1]的LCP(i, j);H[i]=Height[Rank[i]表示Suffix[i]和字典排序在它前一名的后缀子串的LCP大小;
对于正整数i和j而言,最长公共前缀的定义如下:
LCP(i, j) =lcp(Suffix(SA[i]), Suffix(SA[j])) = min(Height[k]|i+1<=k<=j);
也就是计算LCP(i, j)等同于查找Height数组中下表在i+1到j之间的元素最小值
下述例子中如果LCP(0, 3),则最小值为2,则"aadab"和"aabaaaab"的LCP为2
后缀数组的构建:
为了方便比较,创建后缀数组前都会在string的末尾添加一个$字符表示字符串的结束,并且在字典序中最小;
使用常见的排序算法结合strcmp函数构建后缀数组,但strcmp为线性时间复杂度,所以不能体现后缀数组的时间优势;1989,Udi Manber & Gene Myers使用倍增算法(Doubling Algorithm)快速构造后缀数组,其利用了后缀子串之间的联系可将时间复杂度降至O(MlogN),M为模式串的长度,N为目标串的长度;另外基数 排序算法的时间复杂度为O(N);Difference Cover mod 3(DC3)算法(Linear Work Suffix Array Construction)可在O(3N)时间内构建后缀数组;Ukkonen算法(On-line Construction of Suffix-Trees)可在O(N)的时间内构建一棵后缀树,然后再O(N)的时间内将后缀树转换为后缀数组,理论上最快的后缀数组构造法;
结论1:如果Aj =h Ak并且Aj+h <=h Ak+h,则Aj <=2*h Ak (其中j+h<n, k+h<n,=h表示字符串Aj的前h个字符与Ak的前h个字符字典序相等,并且=可以替换成<,<=, =, >, >=)
倍增算法中:输入为string的所有suffix[i];按照<=h进行遍历排序,并且h的值在遍历时取"1,2,4,8,……2^n",每次遍 历保证后缀子串<=h有序;首先对h进行排序;当扩展到<=2h有序的时候,由于2h的前面h个字符已经比较过,所以只需要比较后面的h个字 符,而后面的这h个字符恰好在前一次<=h有序的时候作为其他后缀的前h个字符已经比较过,所以一次遍历中字符串的比较开销为O(N);长度为N的 字符串需要进行logN次遍历(h的值为2^N),直到Rank[i]数组中没有相等的字符串;所以倍增算法的时间复杂度为O(NlogN);其实基数排 序可以有更好的时间复杂度O(N);
给定string:abba,则可以得到suffix[4]的数组:A0=abba, A1=bba, A2=ba, A3=a
当h=1时,按照<=h排序:A0 =h A3 <h A2 =h A1
当
2h=2时,按照<=2h排序:对于A0和A3而言,A3的后半段结束字符$,则直接判定A3较小;A3与A2之间的小于关系不变;对于A1和A2
而言,因为A2 =h A1,所以只要比较a和ba的<=h的比较结果,其就是A3跟A2的<=h的比较结果;利用倍增算法得到suffix[i]的有序数组Rank[i]之后,就可以分别在O(N)的时间复杂度内得到SA[i]数组和H[i]数组;
后缀数组的应用:
最长公共前缀(LCP,Longest Common Prefix)的后缀数组解法:构建SA[i]数组中相邻元素的最长公共前缀(LCP,Longest Common Prefix),Height[i]表示SA[i]和SA[i-1]的LCP;如果需要求解string中的后缀子串suffix[i]和 suffix[j]的LCP,则通过Rank数组取得两个后缀的排名m和n(m<n),则Height数组在m+1和n之间的最小值就是目标的 LCP;
最长回文子串(LPS,Longest Palindrome Substring)的后缀数组解法:如求字符串abcddcef的LPS,则将原字符串翻转并在前面加上$字符,最后连接到源字符串末尾变成 abcddcef$fecddcba,所以LPS转换为求新字符串某两个suffix子串的最长公共前缀;
最长公共子串(LCS,Longest Common Substring)的后缀数组解法:最长公共子串指的是字符必须靠在一起的子串,不同于最长公共子序列;一种解法是动态规划(Dynamic Programming),时间复杂度为O(N^2);一种解法是KMP算法,时间复杂度为O(N^2);一种解法是后缀数组解法,时间复杂度为 O(NlogN);如求字符串S1:abcdefg和字符串S2:kgdefac的LCS,将S2前面加上$字符并连接到S1末尾变成 abcdefg$kgdefac,则LCS也转换为求新字符串中某两个suffic子串的最长公共前缀,但是这两个子串的起始位置必须在$前后;
样例:
const int MAXL = , MAXN = ;
struct SuffixArray {
struct RadixElement {
int id, k[];
} RE[MAXL], RT[MAXL]; int N, A[MAXL], SA[MAXL], Rank[MAXL], Height[MAXL], C[MAXL]; void RadixSort() {
int i, y;
for (y = ; y >= ; y--) {
memset(C, , sizeof(C));
for (i = ; i <= N; i++)
C[RE[i].k[y]++;
for (i = ; i < MAXL; i++)
C[i] += C[i - ];
for (i = N; i >= ; i--)
RT[C[RE[i].k[y]--] = RE[i];
for (i = ; i <= N; i++)
RE[i] = RT[i];
}
for (i = ; i <= N; i++) {
Rank[RE[i].id] = Rank[RE[i - ].id];
if (RE[i].k[] != RE[i - ].k[] || RE[i].k[] != RE[i - ].k[])
Rank[RE[i].id]++;
}
} void CalcSA() {
int i, k;
RE[].k[] = -;
for (i = ; i <= N; i++)
RE[i].id = i, RE[i].k[] = A[i], RE[i].k[] = ;
RadixSort();
for (k = ; k + <= N; k *= ) {
for (i = ; i <= N; i++)
RE[i].id = i, RE[i].k[] = Rank[i], RE[i].k[] =
i + k <= N ? Rank[i + k] : ;
RadixSort();
}
for (i = ; i <= N; i++)
SA[Rank[i] = i;
} void CalcHeight() {
int i, k, h = ;
for (i = ; i <= N; i++) {
if (Rank[i] == )
h = ;
else {
k = SA[Rank[i] - ];
if (--h < )
h = ;
for (; A[i + h] == A[k + h]; h++)
;
}
Height[Rank[i] = h;
}
}
} SA;
参考链接:
http://www.byvoid.com/blog/lcs-suffix-array/
http://dongxicheng.org/structure/suffix-array/
http://wenku.baidu.com/view/3338866b561252d380eb6ed7.html
补充:后缀树(Suffix Tree)
同后缀数组一样,后缀树是解决字符串处理的高效工具;后缀树基于Trie树的基本树形结构:
首先按照后缀的定义生成一个string的所有后缀子串suffix[i],然后构建Trie树,由于在Trie树中一个substring不能是另一个 substring的前缀,所以需要在原始string的末尾加上一个$字符;而后缀树就是包含string所有后缀子串的压缩Trie树 (Compressed Trie Tree);
然后对Trie树进行压缩,原始定义的Trie树中,一条边仅代表一个字符,而对于没有分支的路径则可以将路径上的节点压缩成为一个节点,使得一条边代表多个字符;
接着针对具体问题构建广义后缀树(Generalized Suffix Tree):由于构建后缀树的时候会在string末尾添加结束字符,则如果在不同的string添加不同的结束字符($或者#),则可以在同一棵后缀树中包含多个字符串;
最后寻找最低公共祖先(Lowest Common Ancestor):在后缀树中的LCA对应string中最长公共前缀(Longest Common Prefix),这一操作可以在O(1)完成;
后缀树的应用:
- 从目标串T中判断是否包含模式串P(时间复杂度接近KMP算法);
- 从目标串T中查找最长的重复子串;
- 从目标串T1和T2中查找最长公共子串;
- Ziv-Lampel无损压缩算法;
- 从目标串T中查找最长的回文子串;
参考连接:
http://blog.csdn.net/TsengYuen/article/details/4815921
http://www.allisons.org/ll/AlgDS/Tree/Suffix/
最新文章
- C# DateTime日期格式化
- 【转】java.util.Arrays.asList 的用法
- *HDU2852 树状数组(求第K小的数)
- 基于XMPP的IOS聊天客户端程序
- JAVA魔法堂:折腾Mybatis操作SQLite的SQLException:NYI异常
- [转]Gridview中实现RadioButton单选效果
- linux中的磁盘的MBR记录详解
- sql 无法识别的配置节 system.serviceModel
- percona监控模板图形解释
- xshell中启动linux图形界面
- Memory Analyzer Blog
- js快排与namespace
- 使用XCODE 的SOURCE CONTROL 做版本控制 (1)
- Backbone.js的技巧和模式
- C#WinForm中复制、粘贴文本到剪贴板
- Docker Stack 集群部属服务
- think
- Neject 在MVC框架中使用
- Python操作Mysql数据库进阶篇——查询操作详解(一)
- 计算器的改良(NOIP2000)
热门文章
- 8 个很有用的 jQuery 技巧(转)
- bzoj 4070: [Apio2015]雅加达的摩天楼【spfa】
- 51nod 1188 最大公约数之和 V2
- 大水题(water)
- 【POJ - 1661】Help Jimmy (动态规划)
- 比特币搬砖对冲策略Python源码
- 在JS/jQuery中,怎么触发input的keypress/keydown/keyup事件?
- [HNOI2008]Card洗牌
- 贪心 Codeforces Round #109 (Div. 2) B. Combination
- 题解报告:poj 2299 Ultra-QuickSort(BIT求逆序数)