后缀数组笔记
浏览数：17 /
时间：2015年06月08日
在字符串匹配问题中经常出现这两个概念：
文本(text)：原文
模板(pattern)：关键词（相当于一个子串）
任务：在text中找pattern
常用算法：
AC自动机：多个pattern
KMP：已知pattern，对pattern进行预处理
Trie：也叫前缀树，常用于找字符串前缀
后缀数组：已知text，对text进行预处理
后缀树：其实就是路径压缩版的trie树，把树上没有分叉的路径压缩掉了
-----------------------------------------------------------------
sa[i]：后缀数组，pattern的所有后缀从小到大排序后，排好序的第i个后缀的开头位置（共n个后缀，sa[0..n-1]）
eg：对于单词”banana“，sa={5,3,1,0,4,2}，分别对应后缀a, ana, anana, banana, na, nana
rank[i]：保存sa[i]在所有后缀中从小到大排列的名次
sa[i]与rank[i]互逆，即sa[rank[i]]=i, rank[sa[i]]=i
定义height[i]=sa[i-1]和sa[i]的最长公共前缀长度（即两个排名相邻的后缀的最长公共前缀长度）
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
