Palindrome Detection Using On-line Position
Surangkanang Charoenrak, Supaporn Chairungsee · 2017
The purpose of this study is to detect a reverse substring in any position i of the string y, uRru is a factor of y, uR is a reverse substring of u and r is a substring between uR and u. We develop an efficient algorithm to detect all reverse repetitions in a string and describe the algorithm for computing the Longest Previous reverse Factor (LPrF) table by using the on-line construction of position heap data structure. This algorithm runs in linear time on a fixed size alphabet. For the applications in bioinformatics field, LPrF table can use to detect palindrome and gapped palindrome.