Je dois prouver que dans une chaîne de caractères avec un nombre de caractères n, au plus n sous-chaînes palindromiques distinctes et non vides sont possibles. Je comprends que c'est parce que chaque caractère peut être un palindrome en soi, et donc que le nombre maximum possible de sous-chaînes sera égal au nombre de caractères de la chaîne. Cependant, je ne parviens pas à exprimer cela sous la forme d'une preuve mathématique. Comment puis-je le faire ?
Réponse
Trop de publicités?
Matt Timmermans
Points
3405
Données xc donde x est une chaîne quelconque et c est un caractère quelconque :
Toutes les sous-chaînes de xc qui ne figurent pas déjà dans les x doit être suffixes de xc . S'il s'agit de palindromes, ils sont de la forme cyc donde cy est un suffixe de x y y est un palindrome ou vide.
Imaginons qu'il existe deux nouveaux suffixes palindromiques de ce type. Puisqu'il s'agit de suffixes distincts de la même chaîne, ils doivent être de longueurs différentes. cyczc donde z y ycz sont tous deux palindromes ou vides.
Si ycz est un palindrome, il y a quelques cas à considérer.
-
Si len(y) = len(z), cela implique que y = z et que czc a donc été déjà une sous-chaîne de x -- une contradiction.
-
Si z est plus courte, nous pouvons alors la diviser à nouveau en cz r cwczc mais z est un palindrome, donc z r \= z et nous avons la même contradiction.
-
Si z est plus long, nous pouvons alors le diviser en cycwcy r c , avec wcy r \= z, et c'est un palindrome, donc aussi z = ycw et de nouveau la contradiction que czc apparaît déjà dans x .
Ainsi, l'ajout d'un seul caractère à une chaîne de caractères peut introduire au plus un nouvelle sous-chaîne palindromique. Le nombre total de ces sous-chaînes dans une chaîne ne peut donc pas être supérieur à la longueur de la chaîne.
