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 oft such that Pals(p) = Pals(t[i : i + m - 1]). We present linear-time algorithms to solve this problem. (C) 2012 Elsevier B.V. All rights reserved.
palindromes pattern matching linear time algorithms border arrays suffix trees