如何find最长的回文序列？
这是来自algorithm书（Vazirani）的问题（6.7 ch6 ），与寻找最长回文的经典问题略有不同。 我怎么解决这个问题 ？
如果从左到右或从右到左读取相同的子序列是回文的。 例如，序列
A,C,G,T,G,T,C,A,A,A,A,T,C,G有许多回文子序列，包括
A,C,G,C,A和A,A,A,A（另一方面，子序列A,C,T不是回文）。 devise一个采用序列x[1 ...n]并返回最长回文子序列（的长度）的algorithm。 运行时间应该是O(n^2)
这可以用O（n ^ 2）中的dynamic规划来解决。 基本上，这个问题是关于使用x[i+1...j] ， x[i,...j-1]和x[i+1,...,j-1] x[i...j]的最长子序列构buildx[i...j]最长的回文序列， x[i+1,...,j-1] （如果第一个和最后一个字母相同）。
首先，空string和单个string是平凡的回文。 注意对于一个子串x[i,...,j] ，如果x[i]==x[j] ，我们可以说最长回文的长度是x[i+1,...,j-1]+2的最长回文x[i+1,...,j-1]+2 。 如果它们不匹配，则最长的回文是x[i+1,...,j]和y[i,...,j-1]的最大回文。
这给了我们这个function：
longest(i,j)= j-i+1 if ji<=0, 2+longest(i+1,j-1) if x[i]==x[j] max(longest(i+1,j),longest(i,j-1)) otherwise
你可以简单地实现该函数的memoized版本，或者自下而上编码一个最长的表[i] [j]。
这给你只有最长的子序列的长度，而不是实际的子序列本身。 但是也可以很容易地扩展到做到这一点。
这个问题也可以作为称为LCS（最长公共子序列）问题的一个非常常见的问题的变体来完成。 让inputstring由字符数组s1 [0 … n-1]表示。
1）反转给定的序列，并将反向存储在另一个数组s2 [0..n-1]中，其实质上是s1 [n-1 … 0]
2）给定序列s1和反向序列s2的LCS将是最长的回文序列。
这个解决scheme也是一个O（n ^ 2）解决scheme。
这使我对子string和子string之间的区别有些困惑（见6.8和6.11）。根据我们对子序列的理解，给出的例子没有回文子序列ACGCA。 这是我的伪代码，我不太清楚初始化> <
for 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)
准备algorithm最后…
最长的回文序列的工作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 *给出一个string，我们需要find该string中最长的子序列，它是回文*在这段代码中，我们使用了hashset来确定给定string中唯一的子string集合* /
公共类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; } }
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]; }
对于string中的每个字母：
-
将字母设置为回文中间（当前长度= 1）
-
检查回文多长时间，如果这是它的中间
-
如果这个回文长于我们发现的回文长度（直到现在）：保持回文索引和大小。
O（N ^ 2）：因为我们有一个循环select中间和一个循环，检查回文多长时间，如果这是中间的。 每个循环从0到O（N）[从0到N-1的第一个，第二个从0到（N-1）/ 2]
例如：DBABCBA
i = 0：D是回文的中间，不能长于1（因为它是第一个）
i = 1：B是回文的中间，检查B前后的字符：不相同（D在一边，A在另一边） – >长度为1。
i = 2：A是回文中间，检查字符前后A：都是B – >长度是3.检查字符间距为2：不是identiacl（D在一边，C在另一边） – >长度是3。
等等
input： A1，A2，…，An
目标：find最长的严格递增的子序列（不一定是连续的）。
L（j）：以j结尾的最长严格递增的子序列
L（j）： max{ L(i)}+1 } where i < j and A[i] < A[j]
然后findmax{ L(j) } for all j
你会在这里得到源代码
