Trouver la plus longue sous-séquence Palindrome avec moins de mémoire

Je suis en train d'essayer de résoudre un problème de programmation dynamique de Cormem de Introduction aux Algorithmes 3e édition (page 405) qui demande le suivant:

Un palindrome est une chaîne non vide de plus de
certains alphabet qui lit le même
en avant et en arrière. Des exemples de
les palindromes sont toutes les chaînes de caractères de longueur
1, civic, racecar, et aibohphobia
(la peur de palindromes).

Donner un algorithme efficace pour trouver
le plus long palindrome qui est un
sous-suite d'une chaîne d'entrée.
Par exemple, compte tenu de l'entrée
charactervotre algorithme doit
retour carac.

Eh bien, je pourrais le résoudre de deux manières:

Première solution:

Le plus long Palindrome sous-suite (LPS) d'une chaîne est tout simplement le Plus Longue Sous-Suite Commune de lui-même et de son inverse. (J'ai cette solution après avoir résolu une autre question connexe, qui demande la Plus Longue Sous-Suite Croissante d'une séquence).
Car c'est tout simplement une CL variante, il prend également en O(n2) en temps et O(n2) de la mémoire.

Deuxième solution:

La deuxième solution est un peu plus élaboré, mais aussi suit le général LCS modèle. Il s'agit de la suite de récurrence:

lps(s[i..j]) = 
    s[i] + lps(s[i+1]..[j-1]) + s[j], if s[i] == s[j];
    max(lps(s[i+1..j]), lps(s[i..j-1])) otherwise

Le pseudo-code pour le calcul de la longueur de la lps est la suivante:

compute-lps(s, n):

    //palindromes with length 1
    for i = 1 to n:
        c[i, i] = 1
    //palindromes with length up to 2
    for i = 1 to n-1:
        c[i, i+1] = (s[i] == s[i+1]) ? 2 : 1

    //palindromes with length up to j+1
    for j = 2 to n-1:
        for i = 1 to n-i:
            if s[i] == s[i+j]:
                c[i, i+j] = 2 + c[i+1, i+j-1]
            else:
                c[i, i+j] = max( c[i+1, i+j] , c[i, i+j-1] )

Encore, il faut O(n2) de temps et de mémoire, si je veux effectivement construire le lps (parce que j'ai 'll besoin de toutes les cellules sur la table). L'analyse des problèmes connexes, tels que l'ol, qui peuvent être résolus grâce à des approches autres que LCS-comme avec moins de mémoire (LIS est résoluble avec O(n) de mémoire), je me demandais si il est possible de le résoudre avec O(n) de mémoire, trop.

LIS atteint cette borne en reliant le candidat de sous-séquences, mais avec des palindromes, il est plus difficile parce que ce qui compte ici n'est pas l'élément précédent dans la sous-suite, mais le premier. Personne ne sait si c'est possible de le faire, ou sont les solutions précédentes mémoire optimale?

source d'informationauteur Luiz Rodrigo

  1. 5

    Ici est une mémoire très efficace version. Mais je n'ai pas encore démontré qu'il est toujours O(n) de la mémoire. (Avec une étape de prétraitement de mieux que O(n2) CPU, si O(n2) est le pire des cas.)

    Commencer à partir de la gauche de la position la plus haute. Pour chaque position, suivi d'un tableau de le plus éloigné de la sortie à laquelle vous pouvez générer traduit de sous-séquences de longueur 1, 2, 3, etc. (Ce qui signifie qu'une sous-suite à la gauche de notre point est réfléchie vers la droite.) Pour chaque reflète sous-suite, nous stocker un pointeur vers la partie suivante de la sous-suite.

    Que nous travaillons notre chemin à droite, nous sommes la recherche de l'ERS de la chaîne à la position de toutes les occurrences de l'élément courant, et essayez d'utiliser ces matchs pour améliorer les limites que nous avons déjà eu. Lorsque nous aurons fini, nous regardons la plus longue en miroir sous-suite et nous pouvons facilement construire le meilleur palindrome.

    Considérons ce pour character.

    1. Nous commençons avec notre meilleur palindrome étant la lettre "c", et notre miroir sous-suite étant atteint avec la paire (0, 11) qui sont aux extrémités de la chaîne.
    2. Prochaine considérer le 'c' à la position 1. Notre meilleur miroir de sous-séquences dans la forme (length, end, start) sont maintenant [(0, 11, 0), (1, 6, 1)]. (Je vous laisse la liste, vous avez besoin de générer de trouver effectivement le palindrome.
    3. Prochaine envisager la h à la position 2. Nous n'avons pas d'améliorer les limites [(0, 11, 0), (1, 6, 1)].
    4. Prochaine envisager la a à la position 3. - Nous améliorer les limites de [(0, 11, 0), (1, 6, 1), (2, 5, 3)].
    5. Prochaine envisager la r à la position 4. - Nous améliorer les limites de [(0, 11, 0), (1, 10, 4), (2, 5, 3)]. (C'est là que le liste serait utile.

    De travail à travers le reste de la liste que l'on ne s'améliorent pas de limites.

    Donc nous retrouver avec la plus longue en miroir de la liste est de longueur 2. Et on voudrait suivre la liste chaînée (que je n'ai pas d'enregistrement dans cette description pour le trouver, c'est ac. Depuis les extrémités de cette liste se trouvent à des positions (5, 3) nous pouvons retourner la liste, insérer un caractère 4puis ajouter la liste pour obtenir carac.

    En général, la quantité maximale de mémoire que c'est de stocker toutes les longueurs maximales miroir de sous-séquences, plus la mémoire pour stocker les listes de ladite sous-séquences. Généralement, ce sera une très petite quantité de mémoire.

    À un classique de la mémoire/CPU compromis vous pouvez prétraitement de la liste une fois dans le temps O(n) pour générer un O(n) de la taille de hachage de tableaux de où des éléments de la séquence apparaissent. Cela peut vous permettre de numériser pour "améliorer miroir sous-suite avec ce couplage", sans tenir compte de l'ensemble de la chaîne, qui doit généralement être de réaliser d'importantes économies sur le CPU pour des chaînes plus longues.

  2. 3

    Première solution @Luiz Rodrigo question est erroné: Longest Common Subsesquence (LCS) d'une chaîne et son inverse n'est pas nécessairement un palindrome.

    Exemple: pour la chaîne CBACB, la CABINE est LCS de la chaîne et de son inverse, et il n'est évidemment pas un palindrome.
    Il y a un moyen, cependant, pour le faire fonctionner. Après LCS d'une chaîne et son inverse est construit, prendre à gauche la moitié de celui-ci (y compris le milieu de caractère pour les chaînes de longueur) et de le compléter sur la droite avec inversée de gauche à moitié (pas y compris la mi-personnage si la longueur de la chaîne est impair).
    Il sera évidemment un palindrome et il peut être trivialement prouvé que ce sera une sous-suite de la chaîne.

    - Dessus de la LCS, le palindrome construit de cette façon sera CAC.