Parameterized longest previous factor
- 作者：Richard Beal ; r.beal@computer.org ; Donald Adjeroh don@csee.wvu.edu
- 关键词：Parameterized suffix array ; Parameterized longest common prefix ; p-string ; p-match ; LPF ; LCP
- 刊名：Theoretical Computer Science
- 出版年：2012
- 期刊代码：114_03043975
- 类别：cp
- 出版时间：15 June, 2012
- 卷：437
- 期：Complete
- 页码：21-34
- 文件大小：418 K
摘要
Given a string , the longest previous factor (LPF) problem is to determine the maximum length of a previously occurring factor for each suffix occurring in . The LPF problem is defined for traditional strings exclusively from the constant alphabet . A parameterized string (p-string) is a string composed of symbols from a constant alphabet and a parameter alphabet . We formulate the LPF problem in terms of p-strings by defining the parameterized longest previous factor (pLPF) problem. Subsequently, we present an expected linear time solution to construct the parameterized longest previous factor () array. Given our pLPF solution, we show how to construct the (parameterized longest common prefix) array with the same general algorithm. We exploit the properties of the data structure to also construct the standard (longest previous factor) and (longest common prefix) arrays all in linear time. Further, we provide insight into the practicality of our construction algorithms.