--- jupytext: text_representation: extension: .md format_name: myst format_version: 0.13 jupytext_version: 1.16.0 kernelspec: name: python3 display_name: Python 3 --- # Algorithmes sur les chaînes de caractères ```{code-cell} python :tags: [hide-input] import matplotlib.pyplot as plt import matplotlib.patches as patches import numpy as np import seaborn as sns import time import random import string sns.set_theme(style="whitegrid", palette="muted", font_scale=1.1) ``` ## Introduction Les chaînes de caractères sont omniprésentes en informatique : moteurs de recherche, éditeurs de texte, outils bioinformatiques, détecteurs de plagiat, compilateurs, protocoles réseau. La **recherche de motifs** (*pattern matching*) — trouver toutes les occurrences d'un motif `P` de longueur `m` dans un texte `T` de longueur `n` — est l'opération fondamentale de ce domaine. Sa complexité peut varier de O(nm) pour l'approche naïve à O(n+m) pour les algorithmes sophistiqués que nous étudierons dans ce chapitre. ```{prf:definition} Problème de recherche de motifs :label: definition-17-01 Étant donné un texte `T[0..n-1]` et un motif `P[0..m-1]` sur un alphabet `Σ`, le **problème de recherche de motifs** consiste à trouver toutes les positions `i` telles que `T[i..i+m-1] = P`. On appelle ces positions les **occurrences** du motif dans le texte. ``` Dans ce chapitre, nous étudierons les principaux algorithmes de recherche de motifs, leurs fondements théoriques et leurs domaines d'application. ## Recherche naïve L'algorithme de recherche naïve est le plus simple : pour chaque position `i` du texte, on compare le motif avec le sous-texte `T[i..i+m-1]` caractère par caractère. ```{code-cell} python def recherche_naive(texte, motif): """ Recherche naïve : O(n·m) dans le pire cas. Retourne la liste des positions de début des occurrences. """ n, m = len(texte), len(motif) occurrences = [] comparaisons = 0 for i in range(n - m + 1): j = 0 while j < m and texte[i + j] == motif[j]: comparaisons += 1 j += 1 if j < m: comparaisons += 1 # La comparaison qui a échoué if j == m: occurrences.append(i) return occurrences, comparaisons # Exemple simple texte = "AABAACAADAABAABA" motif = "AABA" occ, cmp = recherche_naive(texte, motif) print(f"Texte : '{texte}'") print(f"Motif : '{motif}'") print(f"Occurrences : {occ}") print(f"Comparaisons : {cmp}") # Pire cas : texte = "AAAA...A", motif = "AAAB" print("\n--- Pire cas ---") n = 100 texte_pire = 'A' * n motif_pire = 'A' * 10 + 'B' occ_pire, cmp_pire = recherche_naive(texte_pire, motif_pire) print(f"Texte de {n} 'A', motif 'A'*10+'B' : {cmp_pire} comparaisons (attendu ≈ {n * 11})") ``` ```{prf:remark} :label: remark-17-01 **Analyse de complexité.** Dans le pire cas (texte et motif composés du même caractère répété, sauf le dernier), l'algorithme naïf effectue `(n - m + 1) · m` comparaisons, soit O(nm). Ce pire cas est atteint par exemple avec `T = "AAAA...A"` et `P = "AAA...AB"`. Dans la pratique, pour des textes en langue naturelle et des motifs courts, la complexité est proche de O(n) car les premières comparaisons échouent rapidement. ``` ## Algorithme de Knuth-Morris-Pratt (KMP) L'algorithme KMP (1977) est la première amélioration fondamentale de la recherche naïve. Son idée clé : lorsqu'une correspondance partielle échoue, ne pas repartir de zéro, mais **réutiliser l'information** accumulée lors de la correspondance partielle. ```{prf:definition} Table des préfixes-suffixes (failure function) :label: definition-17-02 La **table des préfixes-suffixes** `pi` d'un motif `P[0..m-1]` est définie par : `pi[i]` = longueur du plus long préfixe propre de `P[0..i]` qui soit aussi un suffixe de `P[0..i]`. Par convention, `pi[0] = 0`. Cette table encode la structure interne du motif et permet, lors d'un échec à la position `j`, de sauter directement à la position `pi[j-1]` dans le motif plutôt que de revenir à 0. ``` ```{code-cell} python def construire_table_kmp(motif): """ Construit la table des préfixes-suffixes (failure function) de KMP. Complexité : O(m) """ m = len(motif) pi = [0] * m k = 0 # longueur du plus long préfixe-suffixe courant for i in range(1, m): # Réduire k jusqu'à trouver une correspondance ou k=0 while k > 0 and motif[k] != motif[i]: k = pi[k - 1] if motif[k] == motif[i]: k += 1 pi[i] = k return pi def kmp_recherche(texte, motif): """ Algorithme de Knuth-Morris-Pratt. Complexité : O(n + m). Retourne la liste des positions d'occurrence. """ n, m = len(texte), len(motif) if m == 0: return list(range(n + 1)), 0 pi = construire_table_kmp(motif) occurrences = [] comparaisons = 0 q = 0 # nombre de caractères correspondants for i in range(n): comparaisons += 1 while q > 0 and motif[q] != texte[i]: q = pi[q - 1] comparaisons += 1 if motif[q] == texte[i]: q += 1 if q == m: occurrences.append(i - m + 1) q = pi[q - 1] return occurrences, comparaisons # Démonstration de la table KMP motifs_test = ["AAAB", "ABCABD", "AABAABAAB", "ABAB"] for m in motifs_test: pi = construire_table_kmp(m) print(f"Motif : {m}") print(f" pi : {pi}") print() # Comparaison naïf vs KMP texte = "AABAACAADAABAABA" motif = "AABA" occ_kmp, cmp_kmp = kmp_recherche(texte, motif) occ_nv, cmp_nv = recherche_naive(texte, motif) print(f"Texte : '{texte}', motif : '{motif}'") print(f"Naïf : {cmp_nv} comparaisons → {occ_nv}") print(f"KMP : {cmp_kmp} comparaisons → {occ_kmp}") ``` ```{code-cell} python :tags: [hide-input] # Visualisation de la table KMP pour un motif illustratif motif_illus = "ABCABDABCABC" pi_illus = construire_table_kmp(motif_illus) m_illus = len(motif_illus) fig, axes = plt.subplots(2, 1, figsize=(14, 7)) # --- Haut : la table failure --- ax = axes[0] ax.set_title(f'Table des préfixes-suffixes (KMP) — motif : "{motif_illus}"', fontsize=13, fontweight='bold') for i, (c, pi_val) in enumerate(zip(motif_illus, pi_illus)): couleur_fond = '#3498db' if pi_val > 0 else '#ecf0f1' couleur_texte = 'white' if pi_val > 0 else '#2c3e50' rect = patches.FancyBboxPatch((i, 1.2), 0.85, 0.7, boxstyle="round,pad=0.05", edgecolor='#7f8c8d', facecolor=couleur_fond) ax.add_patch(rect) ax.text(i + 0.425, 1.57, c, ha='center', va='center', fontsize=12, fontweight='bold', color=couleur_texte, fontfamily='monospace') rect2 = patches.FancyBboxPatch((i, 0.3), 0.85, 0.7, boxstyle="round,pad=0.05", edgecolor='#7f8c8d', facecolor='#f39c12' if pi_val > 0 else '#ecf0f1') ax.add_patch(rect2) ax.text(i + 0.425, 0.67, str(pi_val), ha='center', va='center', fontsize=11, fontweight='bold', color='white' if pi_val > 0 else '#7f8c8d') ax.text(i + 0.425, 2.1, str(i), ha='center', va='center', fontsize=9, color='#95a5a6') ax.text(-0.6, 1.57, 'P[i] :', ha='right', va='center', fontsize=10, color='#2c3e50') ax.text(-0.6, 0.67, 'π[i] :', ha='right', va='center', fontsize=10, color='#2c3e50') ax.text(-0.6, 2.1, 'i :', ha='right', va='center', fontsize=9, color='#95a5a6') ax.set_xlim(-1, m_illus + 0.5) ax.set_ylim(0, 2.8) ax.axis('off') # --- Bas : comparaison naïf vs KMP sur pire cas --- ax2 = axes[1] ax2.set_title('Nombre de comparaisons : naïf vs KMP (texte "A"×n, motif "A"×k + "B")', fontsize=12, fontweight='bold') tailles = list(range(10, 301, 10)) k = 8 comparaisons_nv = [] comparaisons_kmp = [] for n in tailles: t = 'A' * n p = 'A' * k + 'B' _, c_nv = recherche_naive(t, p) _, c_kmp = kmp_recherche(t, p) comparaisons_nv.append(c_nv) comparaisons_kmp.append(c_kmp) ax2.plot(tailles, comparaisons_nv, 'o-', color='#e74c3c', label='Naïf O(n·m)', linewidth=2) ax2.plot(tailles, comparaisons_kmp, 's-', color='#2ecc71', label='KMP O(n+m)', linewidth=2) ax2.set_xlabel('Longueur du texte n', fontsize=11) ax2.set_ylabel('Nombre de comparaisons', fontsize=11) ax2.legend(fontsize=11) ax2.grid(True, alpha=0.4) plt.tight_layout() plt.show() ``` ```{prf:remark} :label: remark-17-02 **Analyse de la complexité de KMP.** La construction de la table `pi` nécessite O(m) temps. La phase de recherche effectue au plus `2n` comparaisons : on peut le montrer par un argument de potentiel — la valeur `q` (position dans le motif) ne peut augmenter que `n` fois au total (une fois par caractère du texte), et la somme totale des diminutions de `q` (via `pi`) est bornée par le total des augmentations. L'algorithme est donc O(n+m) temps et O(m) espace. ``` ## Algorithme de Rabin-Karp L'algorithme de **Rabin-Karp** (1987) adopte une approche radicalement différente : il calcule une **empreinte** (*hash*) du motif et compare cette empreinte avec celles des sous-chaînes successives du texte. La clé est de recalculer l'empreinte de chaque fenêtre glissante en O(1) grâce à un **hachage glissant**. ```{prf:definition} Hachage glissant (rolling hash) :label: definition-17-03 Pour un texte `T` et une fenêtre de taille `m`, le **hachage glissant** permet de calculer l'empreinte de `T[i+1..i+m]` à partir de celle de `T[i..i+m-1]` en O(1). Avec un polynôme de hachage de base `b` et module `q` : `h(T[i..i+m-1]) = (T[i]·b^{m-1} + T[i+1]·b^{m-2} + ... + T[i+m-1]) mod q` La mise à jour glissante est : `h(T[i+1..i+m]) = (b·(h(T[i..i+m-1]) - T[i]·b^{m-1}) + T[i+m]) mod q` ``` ```{code-cell} python def rabin_karp(texte, motif, base=256, modulo=101): """ Algorithme de Rabin-Karp. Complexité : O(n+m) en moyenne, O(nm) dans le pire cas (nombreuses collisions). """ n, m = len(texte), len(motif) if m > n: return [], 0 occurrences = [] comparaisons = 0 # Puissance b^(m-1) mod q h_puissance = pow(base, m - 1, modulo) # Calcul des empreintes initiales hash_motif = 0 hash_texte = 0 for i in range(m): hash_motif = (base * hash_motif + ord(motif[i])) % modulo hash_texte = (base * hash_texte + ord(texte[i])) % modulo for i in range(n - m + 1): comparaisons += 1 # Comparaison des hash if hash_motif == hash_texte: # Vérification caractère par caractère (éviter les faux positifs) match = True for j in range(m): comparaisons += 1 if texte[i + j] != motif[j]: match = False break if match: occurrences.append(i) # Mise à jour glissante du hash if i < n - m: hash_texte = (base * (hash_texte - ord(texte[i]) * h_puissance) + ord(texte[i + m])) % modulo hash_texte = (hash_texte + modulo) % modulo # Garantir la positivité return occurrences, comparaisons # Test texte = "GEEKS FOR GEEKS" motif = "GEEKS" occ, cmp = rabin_karp(texte, motif) print(f"Texte : '{texte}', motif : '{motif}'") print(f"Occurrences : {occ}") print(f"Comparaisons : {cmp}") # Comparaison des trois algorithmes sur un texte long import time random.seed(42) texte_long = ''.join(random.choices('ACGT', k=10000)) # ADN simulé motif_test = 'ACGTACGT' t0 = time.perf_counter() occ_nv, cmp_nv = recherche_naive(texte_long, motif_test) t_nv = time.perf_counter() - t0 t0 = time.perf_counter() occ_kmp, cmp_kmp = kmp_recherche(texte_long, motif_test) t_kmp = time.perf_counter() - t0 t0 = time.perf_counter() occ_rk, cmp_rk = rabin_karp(texte_long, motif_test) t_rk = time.perf_counter() - t0 print(f"\nTexte ADN ({len(texte_long)} bases), motif '{motif_test}' ({len(motif_test)} bases)") print(f" Naïf : {cmp_nv:6d} comparaisons, {t_nv*1000:.2f} ms, {len(occ_nv)} occurrences") print(f" KMP : {cmp_kmp:6d} comparaisons, {t_kmp*1000:.2f} ms, {len(occ_kmp)} occurrences") print(f" R-K : {cmp_rk:6d} comparaisons, {t_rk*1000:.2f} ms, {len(occ_rk)} occurrences") ``` ```{prf:remark} :label: remark-17-03 **Applications de Rabin-Karp.** L'algorithme de Rabin-Karp brille dans deux scénarios où KMP est moins adapté : 1. **Recherche de plusieurs motifs simultanément.** On calcule les empreintes de tous les motifs et on les stocke dans une table de hachage. À chaque fenêtre glissante, une seule comparaison d'empreinte suffit pour tester tous les motifs en O(1). C'est la base des **détecteurs de plagiat** (MOSS, JPlag) qui recherchent de nombreux fragments de code simultanément. 2. **Recherche bidimensionnelle.** L'empreinte peut s'étendre à des matrices, permettant de rechercher un sous-tableau 2D dans un tableau 2D — application en traitement d'images. ``` ## Algorithme de Boyer-Moore L'algorithme de **Boyer-Moore** (1977) est en pratique le plus rapide pour la recherche de motifs, notamment pour des alphabets de grande taille (textes en langue naturelle). Contrairement à KMP et Rabin-Karp qui progressent de gauche à droite dans le motif, Boyer-Moore compare le motif **de droite à gauche** et utilise deux heuristiques pour effectuer des sauts importants. ```{prf:definition} Heuristiques de Boyer-Moore :label: definition-17-04 **Heuristique du mauvais caractère** (*bad character rule*) : lors d'un désalignement entre `P[j]` et `T[i+j]`, si le caractère `T[i+j]` n'apparaît pas dans `P[0..j-1]`, on peut décaler le motif entièrement au-delà de `T[i+j]`. Sinon, on aligne la dernière occurrence de `T[i+j]` dans le motif avec `T[i+j]`. **Heuristique du bon suffixe** (*good suffix rule*) : si on a réussi à faire correspondre `P[j+1..m-1]` avec `T[i+j+1..i+m-1]` avant l'échec en `j`, on cherche la prochaine occurrence de ce suffixe dans le motif et on décale en conséquence. Le décalage appliqué est le **maximum** des deux heuristiques. ``` ```{code-cell} python def boyer_moore_bad_char(texte, motif): """ Implémentation simplifiée de Boyer-Moore (heuristique du mauvais caractère uniquement). Sous-optimale mais illustrative. """ n, m = len(texte), len(motif) occurrences = [] comparaisons = 0 # Table du mauvais caractère : dernière occurrence de chaque caractère dans le motif bad_char = {} for i, c in enumerate(motif): bad_char[c] = i s = 0 # décalage courant while s <= n - m: j = m - 1 # comparaison de droite à gauche while j >= 0 and motif[j] == texte[s + j]: comparaisons += 1 j -= 1 if j < 0: occurrences.append(s) # Décalage selon le bon suffixe ou la fin du texte saut = m - bad_char.get(texte[s + m], -1) if s + m < n else 1 s += max(1, saut) else: comparaisons += 1 # Décalage selon le mauvais caractère saut = j - bad_char.get(texte[s + j], -1) s += max(1, saut) return occurrences, comparaisons # Test et comparaison texte = "ABAAABCD" motif = "ABC" occ_bm, cmp_bm = boyer_moore_bad_char(texte, motif) occ_kmp2, cmp_kmp2 = kmp_recherche(texte, motif) print(f"Boyer-Moore : {occ_bm} ({cmp_bm} comparaisons)") print(f"KMP : {occ_kmp2} ({cmp_kmp2} comparaisons)") ``` ## Tri de suffixes Le **tableau de suffixes** (*suffix array*) est une structure de données permettant des requêtes de recherche de motifs extrêmement efficaces une fois le texte prétraité. Il est particulièrement utile en bioinformatique, pour l'indexation de textes, et pour calculer la **plus longue sous-chaîne commune** entre deux textes. ```{prf:definition} Tableau de suffixes :label: definition-17-05 Le **tableau de suffixes** `SA` d'un texte `T[0..n-1]` est le tableau des indices de départ de tous les suffixes de `T`, triés par ordre lexicographique. Par exemple, pour `T = "banana"` : - Suffixes : banana, anana, nana, ana, na, a - Triés : a, ana, anana, banana, na, nana - SA = [5, 3, 1, 0, 4, 2] Une fois `SA` construit, on peut rechercher un motif `P` par **recherche binaire** en O(m log n), et avec le tableau LCP (*Longest Common Prefix*), en O(m + log n). ``` ```{code-cell} python def construire_suffix_array_naive(texte): """Construction naïve du tableau de suffixes. Complexité O(n² log n).""" n = len(texte) suffixes = [(texte[i:], i) for i in range(n)] suffixes.sort(key=lambda x: x[0]) return [i for _, i in suffixes] def construire_lcp_array(texte, sa): """ Construction du tableau LCP (Longest Common Prefix) par l'algorithme de Kasai. Complexité O(n). """ n = len(texte) rank = [0] * n for i, suffix_idx in enumerate(sa): rank[suffix_idx] = i lcp = [0] * n k = 0 for i in range(n): if rank[i] == n - 1: k = 0 continue j = sa[rank[i] + 1] while i + k < n and j + k < n and texte[i + k] == texte[j + k]: k += 1 lcp[rank[i]] = k if k > 0: k -= 1 return lcp def recherche_suffix_array(texte, motif, sa): """ Recherche d'un motif par recherche binaire sur le tableau de suffixes. O(m log n). """ n, m = len(texte), len(motif) # Borne inférieure : première position où motif <= suffixe lo, hi = 0, n while lo < hi: mid = (lo + hi) // 2 if texte[sa[mid]:sa[mid]+m] < motif: lo = mid + 1 else: hi = mid debut = lo # Borne supérieure lo, hi = debut, n while lo < hi: mid = (lo + hi) // 2 if texte[sa[mid]:sa[mid]+m] <= motif and texte[sa[mid]:sa[mid]+m] != motif or \ texte[sa[mid]:sa[mid]+m] > motif: hi = mid else: lo = mid + 1 return sorted(sa[debut:lo]) # Démonstration texte_demo = "banana" sa = construire_suffix_array_naive(texte_demo) lcp = construire_lcp_array(texte_demo, sa) print(f"Texte : '{texte_demo}'") print(f"\n{'Rang':>4} {'SA[i]':>5} {'LCP':>5} {'Suffixe'}") print("-" * 35) for i, (sa_i, lcp_i) in enumerate(zip(sa, lcp)): print(f"{i:>4} {sa_i:>5} {lcp_i:>5} {texte_demo[sa_i:]}") # Application : recherche for motif in ['ana', 'an', 'na']: occ = recherche_suffix_array(texte_demo, motif, sa) print(f"\nMotif '{motif}' → occurrences : {occ}") ``` ```{code-cell} python :tags: [hide-input] # Visualisation comparative des algorithmes de recherche fig, axes = plt.subplots(1, 2, figsize=(14, 6)) # --- Gauche : comparaisons sur texte aléatoire (alphabet {A,C,G,T}) --- ax = axes[0] tailles = list(range(500, 5001, 500)) motif_bench = "ACGT" * 3 # longueur 12 resultats = {'Naïf': [], 'KMP': [], 'Rabin-Karp': [], 'Boyer-Moore (BC)': []} for n in tailles: t = ''.join(random.choices('ACGT', k=n)) _, c = recherche_naive(t, motif_bench) resultats['Naïf'].append(c) _, c = kmp_recherche(t, motif_bench) resultats['KMP'].append(c) _, c = rabin_karp(t, motif_bench) resultats['Rabin-Karp'].append(c) _, c = boyer_moore_bad_char(t, motif_bench) resultats['Boyer-Moore (BC)'].append(c) couleurs = {'Naïf': '#e74c3c', 'KMP': '#2ecc71', 'Rabin-Karp': '#3498db', 'Boyer-Moore (BC)': '#f39c12'} marqueurs = {'Naïf': 'o', 'KMP': 's', 'Rabin-Karp': '^', 'Boyer-Moore (BC)': 'D'} for algo, vals in resultats.items(): ax.plot(tailles, vals, marker=marqueurs[algo], color=couleurs[algo], label=algo, linewidth=2, markersize=5) ax.set_xlabel('Longueur du texte n', fontsize=11) ax.set_ylabel('Nombre de comparaisons', fontsize=11) ax.set_title('Comparaisons — texte ADN (alphabet taille 4)', fontsize=12, fontweight='bold') ax.legend(fontsize=9) ax.grid(True, alpha=0.4) # --- Droite : tableau de suffixes illustré pour "mississippi" --- ax2 = axes[1] texte_ms = "mississippi" sa_ms = construire_suffix_array_naive(texte_ms) n_ms = len(texte_ms) ax2.set_title(f'Tableau de suffixes de "{texte_ms}"', fontsize=12, fontweight='bold') ax2.axis('off') ax2.text(0.05, 0.97, 'SA[i]', transform=ax2.transAxes, fontsize=10, fontweight='bold', color='#2c3e50') ax2.text(0.2, 0.97, 'Suffixe', transform=ax2.transAxes, fontsize=10, fontweight='bold', color='#2c3e50') for rang, idx in enumerate(sa_ms): y = 0.89 - rang * 0.082 bg_color = '#d5e8d4' if rang % 2 == 0 else '#f5f5f5' rect = patches.FancyBboxPatch((0.02, y - 0.03), 0.95, 0.075, boxstyle="round,pad=0.01", facecolor=bg_color, edgecolor='#bdc3c7', transform=ax2.transAxes) ax2.add_patch(rect) ax2.text(0.1, y + 0.006, str(idx), transform=ax2.transAxes, fontsize=10, ha='center', va='center', fontfamily='monospace', color='#3498db', fontweight='bold') ax2.text(0.2, y + 0.006, texte_ms[idx:], transform=ax2.transAxes, fontsize=9, ha='left', va='center', fontfamily='monospace', color='#2c3e50') plt.tight_layout() plt.show() ``` ## Implémentation Rust ```rust /// Construit la table des préfixes-suffixes (failure function) de KMP. pub fn construire_table_kmp(motif: &[u8]) -> Vec { let m = motif.len(); let mut pi = vec![0usize; m]; let mut k = 0usize; for i in 1..m { while k > 0 && motif[k] != motif[i] { k = pi[k - 1]; } if motif[k] == motif[i] { k += 1; } pi[i] = k; } pi } /// Recherche KMP : retourne toutes les positions d'occurrence. O(n + m). pub fn kmp_recherche(texte: &[u8], motif: &[u8]) -> Vec { let (n, m) = (texte.len(), motif.len()); if m == 0 || m > n { return vec![]; } let pi = construire_table_kmp(motif); let mut occurrences = Vec::new(); let mut q = 0usize; for (i, &c) in texte.iter().enumerate() { while q > 0 && motif[q] != c { q = pi[q - 1]; } if motif[q] == c { q += 1; } if q == m { occurrences.push(i + 1 - m); q = pi[q - 1]; } } occurrences } /// Hachage glissant de Rabin-Karp. pub fn rabin_karp(texte: &[u8], motif: &[u8]) -> Vec { const BASE: u64 = 256; const MOD: u64 = 101; let (n, m) = (texte.len(), motif.len()); if m > n { return vec![]; } let h_puissance = (0..m - 1).fold(1u64, |acc, _| (acc * BASE) % MOD); let hash_motif = motif.iter().fold(0u64, |acc, &c| (BASE * acc + c as u64) % MOD); let mut hash_texte = texte[..m].iter().fold(0u64, |acc, &c| (BASE * acc + c as u64) % MOD); let mut occurrences = Vec::new(); for i in 0..=(n - m) { if hash_motif == hash_texte && &texte[i..i + m] == motif { occurrences.push(i); } if i < n - m { hash_texte = (BASE * (hash_texte + MOD - (texte[i] as u64 * h_puissance) % MOD) + texte[i + m] as u64) % MOD; } } occurrences } /// Construction naïve du tableau de suffixes. O(n² log n). pub fn suffix_array(texte: &[u8]) -> Vec { let n = texte.len(); let mut indices: Vec = (0..n).collect(); indices.sort_by(|&a, &b| texte[a..].cmp(&texte[b..])); indices } #[cfg(test)] mod tests { use super::*; #[test] fn test_kmp() { let texte = b"AABAACAADAABAABA"; let motif = b"AABA"; let occ = kmp_recherche(texte, motif); assert_eq!(occ, vec![0, 9, 12]); } #[test] fn test_rabin_karp() { let texte = b"GEEKS FOR GEEKS"; let motif = b"GEEKS"; let occ = rabin_karp(texte, motif); assert_eq!(occ, vec![0, 10]); } #[test] fn test_suffix_array() { let texte = b"banana"; let sa = suffix_array(texte); // Les suffixes triés : a, ana, anana, banana, na, nana assert_eq!(sa, vec![5, 3, 1, 0, 4, 2]); } } ``` ## Résumé Dans ce chapitre, nous avons parcouru les principaux algorithmes sur les chaînes de caractères : - L'**algorithme naïf** effectue O(nm) comparaisons dans le pire cas — acceptable pour des textes courts mais inadapté à grande échelle. - L'**algorithme KMP** atteint O(n+m) grâce à la table des préfixes-suffixes `pi`, qui encode la structure interne du motif et permet d'éviter tout retour arrière dans le texte. - L'**algorithme de Rabin-Karp** utilise le hachage glissant pour atteindre O(n+m) en moyenne ; il excelle pour la recherche simultanée de multiples motifs et la détection de plagiat. - L'**algorithme de Boyer-Moore** est le plus rapide en pratique pour les grands alphabets, grâce à ses heuristiques du mauvais caractère et du bon suffixe qui permettent des sauts de plusieurs positions à la fois. - Le **tableau de suffixes** permet, après un prétraitement O(n log n), des requêtes de recherche en O(m log n) et est fondamental en bioinformatique pour l'alignement de séquences. Dans le chapitre suivant, nous aborderons les **classes de complexité** : les notions de P, NP et NP-complétude qui définissent les frontières du calculable et du tractable.