Palindrome pattern matching

A palindrome is a string that reads the same forward and backward. For a string x, let Pals ( x ) be the set of all maximal palindromes of x, where each maximal palindrome in Pals ( x ) is encoded by a pair ( c, r ) of its center c and its radius r. Given a text t of length n and a pattern p of length m, the palindrome pattern matching problem is to compute all positions i of t such that Pals ( p ) = Pals ( t [ i: i + m − 1 ] ). We present linear-time algorithms to solve this problem.

Authors

• Tomohiro I
• Shunsuke Inenaga
• Masayuki Takeda

Keywords

• Palindromes
• Pattern matching
• Linear time algorithms
• Border arrays
• Suffix trees