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 Σ. 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 (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.