Finding Approximate Palindromes in Strings Quickly and Simply

L. Allison

Described are two algorithms to find long approximate palindromes in a string, for example a DNA sequence. A simple algorithm requires O(n)-space and almost always runs in $O(k.n)$…