Key points are not available for this paper at this time.
Despite significant advances in linear-time scanning algorithms, particularly those based wholly or in part on either Cook's linear-time simulation of two-way deterministic pushdown automata or Weiner's algorithm, the problem of recognizing the initial leftmost nonvoid palindrome of a string in time proportional to the length N of the palindrome, examining no symbols other than those in the palindrome, has remained open. The present algorithm solves this problem, assuming that addition of two integers less than or equal to N may be performed in a single operation. Like the Knuth-Morris-Pratt algorithm, it runs in time independent of the size of the input alphabet. The algorithm as presented finds only even palindromes. However, an extension allows one to recognize the initial odd or even palindrome of length 2 or greater. Other easy extensions permit the recognition of strings (wwR) * of even palindromes and of all the initial palindromes. It appears possible that further extension may be used to show that (wwR) * is in a sense recognizable in real time on a reasonably defined random access machine.
Glenn K. Manacher (Tue,) studied this question.