Parameterized longest previous factor
Given a string W, the longest previous factor (LPF) problem is to determine the maximum length of a previously occurring factor for each suffix occurring in W. The LPF problem is defined for traditional strings exclusively from the constant alphabet Sigma. A parameterized string (p-string) is a string composed of symbols from a constant alphabet Sigma and a parameter alphabet Pi. 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 (pLPF) array. Given our pLPF solution, we show how to construct the pLCP (parameterized longest common prefix) array with the same general algorithm. We exploit the properties of the pLPF data structure to also construct the standard LPF (longest previous factor) and LCP (longest common prefix) arrays all in linear time. Further, we provide insight into the practicality of our construction algorithms. (c) 2012 Elsevier B.V. All rights reserved.
lpf p-string lcp parameterized longest common prefix parameterized suffix array p-match