Fastest algorithm for finding the longest palindrome subsequence

First of all we must read a word, and a desired size.

Then we need to find the longest palindrome created by characters in this word used in order.

For example for size = 7 and word = "abcababac" the answer is 7 ("abababa").

Postscript: the size of the word is smaller than 3000.

There's an algorithm named after Manacher's algorithm, which is really fast, a linear time algorithm.

See Wikipedia's reference

Postscript: If you're really familiar with Z Algorithm, you will find that they're alike.

Edit

I've just misunderstood the OP's meaning (but I don't want to delete the proceding information. It's somewhat useful). He means the longest palindrome subsequence of a string, so dynamic programming seems good:
\begin{align*}
f_{j,k}&=\max(f_{j,k+1},f_{j+1,k},2[S_j=S_k]+f_{j+1,k-1}),\qquad jk\\
\end{align*}
where $f_{j,k}$ denotes the length of the longgest palindrome subsequence of $S_{j..k}$, and $[P]$ is Iverson bracket I think it's just like LCS.

StackExchange Computer Science Q#2466, answer score: 6