Cette SAE a constitué mon premier vrai projet algorithmique en Java de l'année, travaillé en binôme sur plusieurs semaines (semaines 48 à 03/2026). L'objectif était ambitieux : implémenter quatre algorithmes de recherche de sous-chaîne (Naïf, KMP, Rabin-Karp, Boyer-Moore), les tester rigoureusement, puis comparer empiriquement leurs performances. Dès le départ, j'ai pris le parti de lire intégralement le sujet avant d'écrire la moindre ligne de code, ce qui m'a permis de comprendre les contraintes structurelles communes à tous les algorithmes : signature identique ArrayList<Integer> nameAlgoSearch(ArrayList<Character> text, String pattern), interdiction des variables globales sauf cpt, utilisation obligatoire de ArrayList<Character> pour le texte.
Ma principale prise de décision technique a concerné l'algorithme de Boyer-Moore, le plus complexe : j'ai choisi de construire les deux tableaux (tableau des sauts et tableau des bons suffixes) séparément et de manière indépendante du texte, avant d'appliquer le max(D1, D2) lors de la recherche. Cette séparation nette a rendu le code plus lisible et plus facile à déboguer. Pour KMP, j'ai investi du temps dans la compréhension de la fonction préfixe fp avant de coder, ce qui m'a évité les erreurs classiques sur les décalages. Mon implication a été constante sur toute la durée de la SAE, notamment sur la partie mesures d'efficacité qui demandait une rigueur méthodologique réelle.
Le sujet lui-même a été ma ressource principale — 14 pages très denses avec des exemples pas à pas pour chaque algorithme, que j'ai relus plusieurs fois pour chaque implémentation. Pour KMP, les explications sur la fonction préfixe et le tableau de correspondance entre U et fp max ont été décisives : comprendre que le décalage optimal est |U| - fp_max m'a demandé de travailler l'exemple de "ABABACA" à la main avant de le coder.
Pour la partie hachage de Rabin-Karp, j'ai dû m'appuyer sur la documentation Java (API ArrayList, codes ASCII) et travailler l'exemple numérique du sujet (base b=101, texte "abracadabra") pour valider ma formule de hachage déroulante avant de l'intégrer au code. La ressource R1.01.P2 sur les techniques de comparaison algorithmique, recommandée dans le sujet, a orienté ma méthode de mesure : placement du compteur cpt dans la boucle la plus imbriquée, génération de textes aléatoires via codes ASCII, et tests sur textes répétitifs de type "AAAAAA..." pour mettre en évidence les cas défavorables de chaque algorithme.
CE2.01 — Formaliser et modéliser des situations complexes : Le problème de la recherche de sous-chaîne a été formalisé dès le départ via une signature commune à tous les algorithmes et une structure de données uniforme (ArrayList<Character>). Pour Boyer-Moore, la modélisation des deux tableaux de décalage indépendamment du texte illustre la capacité à abstraire un problème complexe en sous-problèmes formalisés. Les structures de test (testAlgo, testCasAlgo) ont été conçues pour couvrir les cas limites : motif absent, motif en début/fin de texte, occurrences chevauchantes.