Finding Approximate Palindromes in Strings Quickly and Simply
<|reference_start|>Finding Approximate Palindromes in Strings Quickly and Simply: 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^2)$ but this does not occur with real biological sequences. A more complex algorithm guarantees $O(k.n)$ worst-case time complexity.<|reference_end|>
@article{allison2004finding,
    title={Finding Approximate Palindromes in Strings Quickly and Simply},
    author={L. Allison},
    journal={arXiv preprint arXiv:cs/0412004},
    year={2004},
    number={2004/162},
    archivePrefix={arXiv},
    eprint={cs/0412004},
    primaryClass={cs.DS}
}