The approximate palindrome searching process can be divided into four stages as shown in following figure. The first stage is the initialization step for the unification of the input data. This stage includes removing the redundant elements (such as spacing and line feed) and separating the header and data for the input file. The second stage is to compute the length of the longest exactly palindrome for the input sequence. The program creates a two-dimensional matrix N for storing the paired matching data, which provides the information for the continuously matching region. The third stage expands the two-dimensional matrix N to a three dimensional matrix (add the error bound value as another dimension), and extend the longest exactly palindrome at stage 2 to the longest approximate palindrome. After computing the largest lengths of exactly palindrome and approximate palindrome at stages 2 and 3, respectively, we trace back the matrix N to derive the corresponding paths under the designated error bound at the final stage.


The flowchart of deriving the exact and approximate palindromes.