Algorithme le plus rapide pour trouver la sous-séquence palindrome la plus longue

8

Tout d'abord, nous devons lire un mot et une taille souhaitée.
Ensuite, nous devons trouver le palindrome le plus long créé par les caractères de ce mot utilisé dans l'ordre.
Par exemple, pour size = 7 et word = "abcababac", la réponse est 7 ("abababa").

Postscript: la taille du mot est inférieure à 3000.

algorithms strings subsequences Gilles 'SO- arrête d'être méchant'
la source

Par palindrome max, voulez-vous dire que vous pouvez supprimer des caractères de la chaîne pour quitter un palindrome et que vous souhaitez le palindrome le plus long (ou la suppression minimale)?

1

Dans votre exemple, il y a aussi des cababac de longueur 7. Les caractères supprimés sont alors côte à côte et à la fin. Êtes-vous autorisé à l'une ou l'autre de ces restrictions? Ils simplifient considérablement la recherche.

6

Cela a déjà été répondu sur Stack Overflow: comment trouver la sous-séquence palindromique la plus longue?

@GenericHuman: La meilleure réponse à cette question était bonne pour le chapitre du manuel que le demandeur lisait. Ce n'est pas une bonne réponse pour ce demandeur. Voir cette question: stackoverflow.com/questions/7043778/… à la place.

Neil G

1

Comment la taille est-elle utilisée? Vous dites que vous voulez le "max palindrome", et si le palindrom le plus long est plus long ou plus court que la taille donnée?

Gilles 'SO- arrête d'être méchant'

6

Il y a un algorithme nommé d'après l'algorithme de Manacher, qui est vraiment rapide, un algorithme de temps linéaire.

Voir la référence de Wikipedia

Postscript: Si vous êtes vraiment familier avec l' algorithme Z , vous constaterez qu'ils se ressemblent.

Éditer

J'ai juste mal compris la signification du PO (mais je ne veux pas supprimer les informations de procédure. C'est quelque peu utile). Il signifie la plus longue sous-séquence palindrome d'une chaîne, donc la programmation dynamique semble bonne: où désigne la longueur de la sous-séquence palindrome la plus longue de , et est le support d'Iverson, je pense que c'est comme LCS .

\begin{aligned} f_{j, k} & = max (f_{j, k + 1}, f_{j + 1, k}, 2 [S_{j} = S_{k}] + f_{j + 1, k - 1}), j < k \\ f_{k, k} & = 1 \\ f_{j, k} & = 0, j > k \end{aligned}

$\begin{align*} f_{j,k}&=\max(f_{j,k+1},f_{j+1,k},2[S_j=S_k]+f_{j+1,k-1}),\qquad j<k\\ f_{k,k}&=1\\ f_{j,k}&=0,\qquad j>k\\ \end{align*}$

f_{j, k}

$f_{j,k}$

S_{j . . k}

$S_{j..k}$

[P]

$[P]$

Yai0Phah
la source

4

Vous répondez dans le cas de la sous-chaîne, mais la question concerne les sous-séquences.

Le premier terme ne devrait-il pas être f (j, k-1)?

Abhishek Bansal

5

L'algorithme le plus rapide auquel je peux penser est d'appliquer LCS de manière créative. Il peut résoudre ce problème dans le temps O (N ^ 2) et l'espace O (N ^ 2) où N est la taille de la chaîne.

LCS (S, reverse (S)) vous donnera la plus grande sous-séquence palindromique, car la plus grande sous-séquence palindromique sera la plus grande sous-séquence commune entre la chaîne S et son inverse.

Par exemple,
S = "abcababac"
T = "cababacba" (inverse de S)
LCS (S, T) = "abababa"

Shashwat
la source

Pouvez-vous affirmer que cet algorithme est le plus rapide que l'on puisse trouver, comme le pose la question?

Juho

@Juho: Je ne peux pas. :( C'est l'algorithme le plus rapide que je connaisse. Il a cependant été accepté chez UVA Online Judge ( uva.onlinejudge.org/external/114/11404.html ) et dans ACM les contraintes du problème sont telles que seule la solution optimisée passera. La solution est donc assez rapide, pas sûre de la plus rapide.

Shashwat

2

Le problème de trouver le LPS d'une chaîne peut être converti en trouvant la plus longue séquence commune de deux chaînes. En cela, une chaîne sera d'origine et la seconde sera inverse de la chaîne d'origine.

Le problème de la plus longue conséquence commune est similaire au problème de correspondance de modèle, sauf que vous êtes autorisé à ignorer les caractères dans le texte. De plus, l'objectif est de renvoyer un seul match, ce qui est aussi long que possible.

LCS peut être résolu en utilisant la récursivité et la mémorisation. $O(n^2)$

Il existe un algorithme légèrement plus rapide découvert par Masek et Paterson de complexité temporelle . Lien papier: Masek et Paterson $O(n^2/\lg n)$

Deux autres algorithmes présentés par Hirschberg pour calculer LCS de deux chaînes (taille ) et (taille ). Basé sur l'hypothèse que les symboles qui peuvent apparaître dans ces chaînes proviennent d'un alphabet de taille (ce qui est en fait vrai dans la plupart des cas). Ainsi, les symboles peuvent être stockés en mémoire en utilisant bits , qui tiendront dans un mot de mémoire. deux symboles peuvent être comparés en temps . Le nombre de différents dans la chaîne est désigné par , qui est bien sûr inférieur à la fois à et à . $A$ $n$ $B$ $m$ $t$ $\log(t)$ $O(1)$ $B$ $s$ $m$ $t$

Celui-ci nécessite un temps où est la longueur de LCS. Ceci est utilisé lorsque la longueur du LCS devrait être petite. Lorsque nous résolvons ce problème en utilisant la programmation dynamique, nous constatons que la plupart des entrées de la matrice sont les mêmes, nous pouvons donc utiliser l'idée de programmation dynamique clairsemée. $O(pn + n\lg n)$ $p$
Cet algorithme nécessite temps. Ceci est très efficace lorsque la longueur de LCS est proche de , dans ce cas, elle sera proche de . $O(p(m+1-p)\log n)$ $m$ $O(n \lg n)$

Les procédures et algorithmes détaillés sont expliqués dans l'article de Hirschberg .

Un autre bon algorithme est proposé par Sohel Rahman qui s'exécute en temps , où est le nombre total de paires ordonnées de positions auxquelles les chaînes correspondent. Elle n'est pas applicable lorsque est l'ordre de , mais il existe de nombreux cas où est l'ordre de . Celui-ci utilise le concept RMQ (Range Maximum Query). Lien papier: Rahman $O(R \log\log n)$ $R$ $R$ $O(n^2)$ $R$ $n$

Surendra
la source

@FrankW, merci! J'ai édité la réponse. Maintenant, les liens sont visibles.

Surendra

Votre formatage manquait toujours; veuillez vérifier ma modification pour voir ce qui est possible. Les références d'articles sont toujours mauvaises car elles reposent sur le lien qui fonctionne toujours, pour toujours. Voir ici pour des conseils; le titre, les auteurs et l'année doivent être indiqués (au moins).

Raphael

Deux préoccupations concernant ce que vous écrivez: 1) "nécessite " n'a pas de sens (puisque donne des limites supérieures ), et ignorer cela est probablement faux; Je suppose qu'ils montrent les limites supérieures de ces ordres, mais les algorithmes peuvent même être plus rapides. 2) Dans le dernier paragraphe au moins, vous voulez .

O (\dots)

$O(\dots)$

O

$O$

Ω (n^{2})

$\Omega(n^2)$

Raphael

-1

Il me manque probablement quelque chose, car cela me semble plutôt trivial: essayez de coupler chaque personnage avec un personnage égal. Ensuite, placez le premier caractère de chaque paire sur le côté gauche, l'autre caractère sur le côté droit, et s'il reste des caractères (c.-à-d. Des caractères non associés à un autre), choisissez-en un et placez-le dans le milieu.

la source

1

Lorsque vous avez (avec les mots ), comment vous si le premier et le dernier caractère du palindrome doivent être ou ? Vous devez examiner le contenu de avant de prendre une décision si vous souhaitez avoir le palindrome le plus long.

a u b v a w b

$aubvawb$

u, v, w

$u,v,w$

a

$a$

b

$b$

u, v, w

$u,v,w$

Algorithme le plus rapide pour trouver la sous-séquence palindrome la plus longue

Réponses: