Sous-chaîne

" chaîne " est une sous-chaîne de " sous-chaîne "

En théorie des langages formels et en informatique , une sous-chaîne est une séquence contiguë de caractères au sein d'une chaîne . Par exemple, « the best of » est une sous-chaîne de « It was the best of times ». En revanche, « Itwastimes » est une sous-séquence de « It was the best of times », mais n'est pas une sous-chaîne.

Les préfixes et les suffixes sont des cas particuliers de sous-chaînes. Un préfixe d'une chaîne est une sous-chaîne de cette chaîne qui apparaît au début de celle-ci ; de même, un suffixe d'une chaîne est une sous-chaîne qui apparaît à la fin de celle-ci .

Les sous-chaînes de la chaîne « apple » seraient : « a », « ap », « app », « appl », « apple », « p », « pp », « ppl », « pple », « pl », « ple », « l », « le », « e », « » (notez la chaîne vide à la fin).

Exemple : La chaîne est égale aux sous-chaînes (et sous-séquences) de à deux décalages différents : banane ||||| ana|| ||| ana La première occurrence est obtenue avec et , tandis que la seconde occurrence est obtenue avec et étant la chaîne vide. Une sous-chaîne d'une chaîne est un préfixe d'un suffixe de cette chaîne, et inversement, un suffixe d'un préfixe ; par exemple, « a » nan est un préfixe de « nana a », qui est lui-même un suffixe de « a banana ». Si « a » est une sous-chaîne de « a » , c'est également une sous-séquence, ce qui est un concept plus général. Les occurrences d'un motif donné dans une chaîne donnée peuvent être trouvées grâce à un algorithme de recherche de chaînes . Trouver la plus longue chaîne qui soit une sous-chaîne de deux chaînes ou plus est connu sous le nom de problème de la plus longue sous-chaîne commune . Dans la littérature mathématique, les sous-chaînes sont également appelées sous-mots ou facteurs . Exemple : La chaîne ban est égale à un préfixe (et une sous-chaîne et une sous-séquence) de la chaîne banana : banane ||| interdire Le symbole de sous-ensemble carré est parfois utilisé pour indiquer un préfixe, de sorte que indique que est un préfixe de . Ceci définit une relation binaire sur les chaînes de caractères, appelée relation de préfixe, qui est un type particulier d' ordre de préfixe .

Suffixe

Une chaîne est un suffixe d'une chaîne s'il existe une chaîne telle que . Un suffixe propre d'une chaîne n'est pas égal à la chaîne elle-même. Une interprétation plus restrictive est qu'il n'est pas vide non plus. $arbre des suffixes d'une chaîne de caractères est une structure de données de type trie qui représente tous ses suffixes. Les arbres de suffixes sont largement utilisés dans les algorithmes de traitement de chaînes . Le tableau des suffixes est une version simplifiée de cette structure de données ; il liste les positions de début des suffixes par ordre alphabétique et possède de nombreuses applications similaires.$

Frontière

Une bordure est un suffixe et un préfixe de la même chaîne, par exemple " " est une bordure de " " (et aussi de " ").

Une chaîne de caractères contenant toutes les permutations possibles d'un ensemble de caractères spécifié est appelée une superpermutation .