15-2 Longest palindrome subsequence

A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes are all strings of length \(1\), \(\text{civic}\), \(\text{racecar}\), and \(\text{aibohphobia}\) (fear of palindromes).

Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input \(\text{character}\), your algorithm should return \(\text{carac}\). What is the running time of your algorithm?

Let \(A[1..n]\) denote the array which contains the given word. First note that for a palindrome to be a subsequence we must be able to divide the input word at some position \(i\), and then solve the longest common subsequence problem on \(A[1..i]\) and \(A[i + 1..n]\), possibly adding in an extra letter to account for palindromes with a central letter. Since there are \(n\) places at which we could split the input word and the \(\text{LCS}\) problem takes time \(O(n^2)\), we can solve the palindrome problem in time \(O(n^3)\).

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用