Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.4k views
in Technique[技术] by (71.8m points)

algorithm - how to find longest palindromic subsequence?

Here is the problem (6.7 ch6 ) from Algorithms book (by Vazirani) that slightly differs from the classical problem that finding longest palindrome. How can I solve this problem ?

A subsequence is palindromic if it is the same whether read left to right or right to left. For instance, the sequence

A,C,G,T,G,T,C,A,A,A,A,T,C,G

has many palindromic subsequences, including A,C,G,C,A and A,A,A,A (on the other hand, the subsequence A,C,T is not palindromic). Devise an algorithm that takes a sequence x[1 ...n] and returns the (length of the) longest palindromic subsequence. Its running time should be O(n^2)

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

This can be solved in O(n^2) using dynamic programming. Basically, the problem is about building the longest palindromic subsequence in x[i...j] using the longest subsequence for x[i+1...j], x[i,...j-1] and x[i+1,...,j-1] (if first and last letters are the same).

Firstly, the empty string and a single character string is trivially a palindrome. Notice that for a substring x[i,...,j], if x[i]==x[j], we can say that the length of the longest palindrome is the longest palindrome over x[i+1,...,j-1]+2. If they don't match, the longest palindrome is the maximum of that of x[i+1,...,j] and y[i,...,j-1].

This gives us the function:

longest(i,j)= j-i+1 if j-i<=0,
              2+longest(i+1,j-1) if x[i]==x[j]
              max(longest(i+1,j),longest(i,j-1)) otherwise

You can simply implement a memoized version of that function, or code a table of longest[i][j] bottom up.

This gives you only the length of the longest subsequence, not the actual subsequence itself. But it can easily be extended to do that as well.



与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...