Lloyd Allison, Technical Report 2004/162, arxiv:cs.DS/0412004,
School of Computer Science and Software Engineering, Monash University, Clayton, Victoria, Australia 3800.
23 Nov. 2004 (draft 19 Sept.)

Abstract: 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)-time where n is the length of the string and k is the number of ''errors'' allowed in the palindrome. Its worst-case time-complexity is O(n²) but this does not occur with real biological sequences. A more complex algorithm guarantees O(k.n) worst-case time complexity.

See [arxiv:cs.DS/0412004][12/'04] & [software.java] of the 1st algorithm.