Détecteur de sous-chaîne répétée

De nombreux problèmes d'entretien et contrôles de nettoyage de données posent une question simple : cette chaîne n'est-elle qu'un fragment plus court écrit encore et encore ? Des chaînes comme ababab, aaaa et xyzxyzxyz sont construites ainsi ; abc et aba ne le sont pas. Ce détecteur de motif de sous-chaîne répétée accepte un unique champ texte non vide, exécute une analyse déterministe de bordure KMP (plus long préfixe-suffixe propre) et renvoie la plus petite unité répétitive avec le nombre exact de répétitions. Aucun appel réseau, aucun hasard, aucune dépendance à l'horloge — uniquement une arithmétique de chaînes que vous pouvez rejouer octet par octet.

Qu'est-ce qu'un motif de sous-chaîne répétée et comment l'unité est choisie

Une chaîne présente un motif de sous-chaîne répétée lorsqu'elle égale une unité non vide écrite bout à bout au moins deux fois, sans caractères restants. Par exemple, ababab est l'unité ab écrite trois fois, aaaa est l'unité a écrite quatre fois et xyzxyz est l'unité xyz écrite deux fois. Le détecteur renvoie toujours la plus petite unité de ce type : si une chaîne peut être pavée par ab et par abab, la réponse est ab avec un compte plus grand, et non le candidat plus long.

Lorsqu'aucune unité plus courte ne couvre la longueur totale, la chaîne est signalée comme non répétée : unit égale le texte d'origine et count vaut un. Le test classique en temps linéaire construit la table KMP du plus long préfixe-suffixe propre pour la chaîne de longueur n, définit period comme n moins la longueur de la bordure finale et vérifie si period divise n et est strictement plus petit que n.

Si les deux conditions tiennent, l'unité est le préfixe de longueur period et le compte est n divisé par period. Cela correspond au balayage par force brute des diviseurs qui essaie chaque longueur de un jusqu'au plancher de n sur deux, mais reste O(n) et ne dépend jamais d'horloges flottantes ni de graines aléatoires.

Les chaînes d'un seul caractère et les résultats vides de validation sont traités explicitement : la longueur un ne peut pas être une répétition non triviale, et un texte vide ou manquant est rejeté avant tout travail LPS.

Où un détecteur de motif répété trouve son utilité

La préparation aux entretiens et les cours d'algorithmes utilisent ce problème pour enseigner bordures, périodes et arguments de diviseurs ; un détecteur en direct permet aux étudiants de vérifier ababab face à aba sans construire à la main des tables LPS sous pression de temps. Les enseignants et auteurs de LMS ont besoin d'un oracle déterministe qui renvoie à la fois l'indicateur booléen du motif et l'unité concrète, afin que les correcteurs automatiques acceptent toute explication correcte nommant le même plus petit fragment.

Les pipelines de qualité des données signalent des colonnes qui ressemblent à des répétitions accidentelles de copier-coller (SKU SKU SKU, yesyesyes) avant qu'elles ne polluent index de recherche ou analytique. Les démonstrations de compression et d'encodage illustrent une structure de type run-length sans prétendre être un compresseur complet : montrer que xyzxyzxyz sont trois copies de xyz suffit souvent pour une diapositive de cours. Une validation échouée ne consomme pas le solde.