Formations — 1 037 leçons en français

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

split prend 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… ».

Lire l'explication détaillée et faire le quiz →

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.