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

Ответ 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

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

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

Ответ 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).

Ответ 3

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

Ответ 4

Меня немного смущает разница между подстрокой и подпоследовательностью (см. Ex6.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)

подготовка окончательного алгоритма...

Ответ 5

import java.util.HashSet;

импортировать 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;
    }
}

Ответ 6

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

Ответ 7

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

• установите букву как середину палиндрома (текущая длина = 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 - середина палиндрома, проверьте char до и после B: не идентичны (D в одной стороне и A в другом) → длина равна 1.

i = 2: A - середина палиндрома, проверьте char до и после A: обе длины B → - 3. проверьте символы с разрывом 2: not identiacl (D в одной стороне и C в другое) → длина 3.

и т.д..

Ответ 8

Вход: 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

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