Palindromes et plsc — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 8)

Palindromes et plsc

Séquences et chaînes de caractères · niveau 2

Énoncé

Soit $S$ la séquence $S$ lue à l'envers.

Montrer que toute sous-séquence palindrome de $S$ est une sous-séquence commune à $S$ et $S$ . En déduire $l_{plsp} (S) \leq l (S, S)$ .
On admet l'égalité des deux longueurs. Une plsc à $S$ et $S$ est-elle toujours un palindrome ? Étudier $S = abcab$ .

Si $P$ est une sous-séquence palindrome de $S$ , alors $P$ est une sous-séquence de $S$ ; or $P = P$ . Donc $P$ est commune à $S$ et $S$ , et sa longueur est au plus $l (S, S)$ .
Non. Pour $S = abcab$ , $S = bacba$ et $l (S, S) = 3$ . Le programme du cours retourne aba (et bab si l'on préfère la gauche), deux palindromes ; mais bca est aussi une plsc ( $S$ : b, c, a aux indices $1, 2, 3$ ; $S$ : indices $0, 2, 4$ ), et ce n'est pas un palindrome. La longueur est la bonne, la séquence ne l'est pas toujours : d'où la récurrence propre aux palindromes du cours.


nom : S
valeurs : a b c a b
vert : 1 2 3


valeurs : b a c b a
vert : 0 2 4
legende : S lue à l'envers : bca est commune, mais pas un palindrome