Using Suffix Tray and Longest Previous Factor for Pattern Searching
Jongsuk Kongsen, Supaporn Chairungsee · 2017
Finding patterns in genomic sequences needs an effective searching algorithm. Although there are different types of string repetition such as tandem repeat, palindrome, or clumps, we are interested in searching for the pattern occurrences in a sequence which can be overlapped. We propose a new algorithm constructed with the suffix tray data structure to ensure the linear time running. We present the algorithm to compute the Longest Previous Factor of a string from its suffix tray. We also apply the notion of suffix links and the attribute m. The proposed algorithm to compute the Longest Previous Factor table of the text, t, of length n requires O(n) time.