Accueil › Coding & algorithmique › Sous-chaînes, découpage et recherche
Sous-chaînes, découpage et recherche
Les chaînes de caractèresdebutant
Sous-chaîne (contiguë) et sous-séquence (ordre conservé, caractères possiblement sautés) sont deux choses différentes. C'est la première question à poser si l'énoncé est ambigu : les algorithmes n'ont rien à voir.
Extraire :
s.substring(2); // du caractère 2 à la fin
s.substring(2, 5); // indices 2, 3, 4 — la fin est exclue
s.indexOf("ab"); // -1 si absent
s.startsWith("pre"); s.endsWith("fin"); s.contains("ab");
Découper — et le piège :
"a.b.c".split("."); // ✗ tableau vide : « . » est un métacaractère regex
"a.b.c".split("\\."); // ✓ [a, b, c]
"a, b ,c".split("\\s*,\\s*");// ✓ gère les espaces autour des virgules
"a,b,,".split(","); // [a, b] — les vides de fin sont supprimés
"a,b,,".split(",", -1); // [a, b, , ] — limite négative : tout conservé
La fenêtre glissante résout la famille « la plus longue sous-chaîne qui… » :
// Plus longue sous-chaîne sans caractère répété
static int plusLongueSansRepetition(String s) {
Map<Character, Integer> dernierIndex = new HashMap<>();
int meilleur = 0, gauche = 0;
for (int droite = 0; droite < s.length(); droite++) {
char c = s.charAt(droite);
if (dernierIndex.containsKey(c))
gauche = Math.max(gauche, dernierIndex.get(c) + 1); // Math.max : ne jamais reculer
dernierIndex.put(c, droite);
meilleur = Math.max(meilleur, droite - gauche + 1);
}
return meilleur;
}
Le Math.max sur gauche est le détail qui rend l'algorithme juste : sans lui, le bord gauche peut reculer et compter deux fois des caractères.
Les termes à connaître
- Sous-chaîne (*substring*)
Une suite contiguë de caractères. À distinguer d'une sous-séquence, qui peut sauter des caractères — la confusion change complètement l'algorithme.
- Sous-séquence
Des caractères pris dans l'ordre mais pas forcément contigus : « ace » est une sous-séquence de « abcde », pas une sous-chaîne.
- Préfixe commun
Le début partagé par plusieurs chaînes. Se calcule en comparant caractère par caractère, avec sortie à la première différence.
- split et regex
splitprend une expression régulière, pas une chaîne littérale :split(".")ne découpe pas sur le point mais sur n'importe quel caractère.- indexOf
Recherche naïve en O(n·m) dans le pire cas. Suffisante en entretien ; KMP ou Boyer-Moore ne sont attendus que si l'énoncé l'exige explicitement.
- Fenêtre glissante
Deux indices qui délimitent une plage contiguë qu'on étend et rétrécit. La technique de référence pour « la plus longue sous-chaîne qui… ».
Cette page présente la partie essentielle de la leçon. Les exemples commentés, les pièges courants et les trois questions de quiz sont dans l'application.