как найти самую длинную палиндромную подпоследовательность?

Question

Вот проблема (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 не является палиндромной).Разработайте алгоритм, который принимает последовательность x[1 ...n] и возвращает (длину) самую длинную палиндромную подпоследовательность.Время его работы должно быть O(n^2)

Answer 1

Это можно решить в 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

Вы можете просто реализоватьзапомненную версию этой функции или закодируйте таблицу с самой длинной [i] [j] снизу вверх.

Это дает вам только длину самой длинной подпоследовательности, а не саму фактическую подпоследовательность.Но это может быть легко расширено, чтобы сделать это также.

---

Answer 2

Эту проблему также можно решить как вариант очень распространенной проблемы, называемой проблемой LCS (Longest Common sub sequence). Пусть входная строка будет представлена ​​массивом символов s1 [0 ... n-1].

1) Обратно заданной последовательности и сохраните обратное в другом массиве, скажем, s2 [0..n-1], который по сути является s1 [n-1 .... 0]

2) LCS данной последовательности s1 и обратной последовательности s2 будет самой длинной палиндромной последовательностью.

Это решение также является решением O (n ^ 2).

Answer 3

Меня немного смущает, что разница между подстрокой и подпоследовательностью (см. Примеры 6.8 и 6.11) Согласно нашему пониманию подпоследовательности, приведенный пример не имеет палиндромной подпоследовательности ACGCA. Вот мой псевдокод, я не совсем уверен насчет инициализации> <</p>

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)

готовится к окончательному алгоритму ...

Answer 4

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];
}

Answer 5

import java.util.HashSet;

import java.util.Scanner;

/ ** * @param args * Нам дана строка, и нам нужно найти самую длинную подпоследовательность в этой строке, которая является палиндромом * В этом коде мы использовали hashset для определения уникального набора подстрок в заданных строках * /

открытый класс 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;
    }
}

Answer 6

Рабочая реализация 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));           
    }
}

Answer 7

Ввод: A1, A2, ...., An

Цель: Найти самую длинную строго возрастающую подпоследовательность (не обязательно смежную).

L (j): Самая длинная строго возрастающая подпоследовательность, заканчивающаяся на j

L (j): max{ L(i)}+1 } where i < j and A[i] < A[j]

Затем найдитеmax{ L(j) } for all j

Вы получите исходный код здесь

Answer 8

для каждой буквы в строке:

• установить букву как середину палиндрома (текущая длина = 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.

и т.д..