这里是一道问题（6.7 ch6）来自Vazirani的算法书，与经典的找到最长回文串问题略有不同。我该如何解决这个问题？
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,Ghas many palindromic subsequences, including
A,C,G,C,AandA,A,A,A(on the other hand, the subsequenceA,C,Tis not palindromic). Devise an algorithm that takes a sequencex[1 ...n]and returns the (length of the) longest palindromic subsequence. Its running time should beO(n^2)
这个问题可以使用动态规划在O(n^2)的时间复杂度内解决。基本上，这个问题是关于在x[i...j]中构建最长回文子序列，使用x[i+1...j]，x[i,...j-1]和x[i+1,...,j-1]（如果第一个和最后一个字母相同）的最长子序列。
首先，空字符串和单个字符字符串都是回文的。注意，对于子串x[i,...,j]，如果x[i]==x[j]，我们可以说最长回文的长度是x[i+1,...,j-1]+2的最长回文。如果它们不匹配，则最长回文是x[i+1,...,j]和y[i,...,j-1]中的最大值。
这给了我们以下函数：
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
2 + ...，如果 j-i<=1 则为 j-i。 - Chris Hopmanfor i = 1 to n do
for j = 1 to i-1 do
L(i,j) = 0
for i = 1 to n do
L(i,i) = 1
for i = n-1 to 1 do //pay attention to the order when filling the table
for j = i+1 to n do
if x[i] = x[j] then
L(i,j) = 2 + L(i+1, j-1)
else do
L(i,j) = max{L(i+1, j), L(i, j-1)}
return max L(i,j)
private static int findLongestPalindromicSubsequence(String string) {
int stringLength = string.length();
int[][] l = new int[stringLength][stringLength];
for(int length = 1; length<= stringLength; length++){
for(int left = 0;left<= stringLength - length;left++){
int right = left+ length -1;
if(length == 1){
l[left][right] = 1;
}
else{
if(string.charAt(left) == string.charAt(right)){
//L(0, n-1) = L(1, n-2) + 2
if(length == 2){
// aa
l[left][right] = 2;
}
else{
l[left][right] = l[left+1][right-1]+2;
}
}
else{
//L(0, n-1) = MAX ( L(1, n-1) , L(0, n-2) )
l[left][right] = (l[left+1][right] > l[left][right-1])?l[left+1][right] : l[left][right-1];
}
}
}
}
return l[0][stringLength-1];
}
最长回文序列的Java工作实现
public class LongestPalindrome
{
int max(int x , int y)
{
return (x>y)? x:y;
}
int lps(char[] a ,int i , int j)
{
if(i==j) //If only 1 letter
{
return 1;
}
if(a[i] == a[j] && (i+1) == j) // if there are 2 character and both are equal
{
return 2;
}
if(a[i] == a[j]) // If first and last char are equal
{
return lps(a , i+1 , j-1) +2;
}
return max(lps(a,i+1 ,j),lps(a,i,j-1));
}
public static void main(String[] args)
{
String s = "NAMAN IS NAMAN";
LongestPalindrome p = new LongestPalindrome();
char[] c = s.toCharArray();
System.out.print("Length of longest seq is" + p.lps(c,0,c.length-1));
}
}
import java.util.HashSet;
import java.util.Scanner;
/** * @param args * 我们有一个字符串，需要找到其中最长的回文子序列 * 在这段代码中，我们使用了哈希集来确定给定字符串中唯一的子字符串集合 */
public class NumberOfPalindrome {
/**
* @param args
* Given a string find the longest possible substring which is a palindrome.
*/
public static HashSet<String> h = new HashSet<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
for(int i=0;i<=s.length()/2;i++)
h.add(s.charAt(i)+"");
longestPalindrome(s.substring(0, (s.length()/2)+(s.length()%2)));
System.out.println(h.size()+s.length()/2);
System.out.print(h);
}
public static void longestPalindrome(String s){
//System.out.println(s);
if(s.length()==0 || s.length()==1)
return;
if(checkPalindrome(s)){
h.add(s);
}
longestPalindrome(s.substring(0, s.length()-1));
longestPalindrome(s.substring(1, s.length()));
}
public static boolean checkPalindrome(String s){
//System.out.println(s);
int i=0;int j=s.length()-1;
while(i<=j){
if(s.charAt(i)!=s.charAt(j))
return false;
i++;j--;
}
return true;
}
}
编写程序从给定字符串中查找最长回文子串。
package source;
import java.util.ArrayList;
public class LongestPalindrome
{
//Check the given string is palindrome by
public static boolean isPalindrome (String s)
{
StringBuffer sb = new StringBuffer(s);
if(s.equalsIgnoreCase(sb.reverse().toString()))
return true;
else
return false;
}
public static void main(String[] args)
{
//String / word without space
String str = "MOMABCMOMOM"; // "mom" //"abccbabcd"
if(str.length() > 2 )
{
StringBuffer sb = new StringBuffer();
ArrayList<String> allPalindromeList = new ArrayList<>();
for(int i=0; i<str.length(); i++)
{
for(int j=i; j<str.length(); j++)
{
sb.append(str.charAt(j));
if( isPalindrome(sb.toString()) ) {
allPalindromeList.add(sb.toString());
}
}
//clear the stringBuffer
sb.delete(0, sb.length());
}
int maxSubStrLength = -1;
int indexMaxSubStr = -1;
int index = -1;
for (String subStr : allPalindromeList) {
++index;
if(maxSubStrLength < subStr.length()) {
maxSubStrLength = subStr.length();
indexMaxSubStr = index;
}
}
if(maxSubStrLength > 2)
System.out.println("Maximum Length Palindrome SubString is : "+allPalindromeList.get(indexMaxSubStr));
else
System.out.println("Not able to find a Palindrome who is three character in length!!");
}
}
}
对于字符串中的每个字母：
将该字母设置为回文的中心（当前长度=1）
检查如果这是回文的中心，它会有多长
如果这个回文比我们找到的更长（直到现在为止）：保留回文的索引和大小。
O（N ^ 2）：因为我们有一个循环选择中心和一个循环检查回文是否为中心。每个循环从0到O（N）运行[第一个循环从0到N-1，第二个循环从0到（N-1）/2]
例如： D B A B C B A
i = 0: D是回文的中心，不能比1更长（因为它是第一个）
i = 1：B是回文的中心，检查B之前和之后的字符：不相同（一侧为D，另一侧为A）-->长度为1。
i=2：A是回文的中间字符，检查A前后的字符：都是B --> 长度为3。检查间隔为2的字符：不相同（一侧为D，另一侧为C）--> 长度为3。
等等。
输入：A1，A2，....，An
目标：找到最长的严格递增子序列（不一定连续）。
L(j)：以j结尾的最长严格递增子序列
L(j)：max{ L(i)}+1 }其中i < j且A[i] < A[j]
然后找到所有j的max{ L(j) }
您可以在这里获取源代码
abcxxba有abcba作为最长的回文子序列 - 这是否正确？因为在这种情况下，被接受的答案对我来说是错误的... - Floris