Given a string, find the shortest prefix that is an even palindrome, in linear time.
The problem can be seen as asking for a minimum overlap of S and S^R. Then we can slide S^R to match a prefix of S by using Knuth-Morris-Pratt's algorithm to achieve O(n) time.
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment