" 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î...
Worldlex WikiContenu en francaisLecture gratuite
" 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îneest une sous-chaîne dequi se produit au début de; de même, un suffixe d'une chaîne de caractèresest une sous-chaîne qui apparaît à la fin de.
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).
est une sous-chaîne (ou un facteur) d'une chaînes'il existe deux chaînes de caractèresettel queEn particulier, la chaîne vide est une sous-chaîne de toute chaîne.
Exemple : La chaîneest égal aux sous-chaînes (et sous-séquences) deà deux décalages différents :
banane ||||| ana|| ||| ana
La première occurrence est obtenue avecet, 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 de manière équivalente, un suffixe d'un préfixe ; par exemple, « sous-chaîne » nanest un préfixe de « sous-chaînenana », qui est lui-même un suffixe de « sous-chaîne » banana.est une sous-chaîne deIl s'agit également d'une sous-séquence , concept plus général. Les occurrences d'un motif donné dans une chaîne de caractères peuvent être trouvées grâce à un algorithme de recherche de chaînes . Trouver la plus longue chaîne égale à 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 . En mathématiques, les sous-chaînes sont aussi appelées sous-mots ou facteurs .est un préfixe d'une chaînes'il existe une chaînetel queUn préfixe valide d'une chaîne de caractères n'est pas égal à la chaîne elle-même ; certaines sources exigent en outre qu'un préfixe valide soit non vide. Un préfixe peut être considéré comme un cas particulier de sous-chaîne.
Exemple : La chaîne banest é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 queindique queest 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 cordeest un suffixe d'une chaînes'il existe une chaînetel queLe suffixe valide d'une chaîne de caractères n'est pas égal à la chaîne elle-même. Plus précisément, il n'est pas vide.Un suffixe peut être considéré comme un cas particulier de sous-chaîne.
Exemple : La chaîne nanaest égale à un suffixe (et une sous-chaîne et une sous-séquence) de la chaîne banana:
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 est une seule chaîne qui contient toutes les chaînes de caractères decomme sous-chaîne. Par exemple,est une superchaîne de, etest plus court. Concaténer tous les membres de, dans un ordre arbitraire, obtient toujours une superchaîne triviale deTrouver des supercordes dont la longueur est la plus petite possible est un problème plus intéressant.
Une chaîne de caractères contenant toutes les permutations possibles d'un ensemble de caractères spécifié est appelée une superpermutation .
Worldlex Wiki