Nora écrit une bande fictive où a et b désignent deux tâches créées pour la maison. Camille lui demande d'en retrouver tous les fragments contigus, sans confondre une forme de fragment et ses positions. Elles choisiront ensuite une répétition à garder, puis une autre qui puisse occuper deux endroits sans partager une lettre. Rien ici ne relève des gestes réellement effectués ni d'un texte familial observé. La bande de départ est ababa ; les positions commencent à zéro et aucune lettre n'est séparée de sa voisine par un espace caché.
Leifheit présente une catégorie consacrée à la maison propre.
Brabantia présente des accessoires de cuisine dans sa navigation.
Bissell présente des appareils pour le nettoyage des tapis.
Ces pages nomment des catégories de produits. Aucun alphabet, fragment, classement de lettres ni calcul de répétition ne vient de leurs textes. Les images n'ont pas été examinées ; la bande et ses demandes sont créées pour Nora.
Les fins de la bande ont des positions avant d'avoir des rangs
Camille prépare une liste de suffixes : pour chaque position de départ, prendre toutes les lettres jusqu'à la fin. Elle obtient ababa en zéro, baba en un, aba en deux, ba en trois et a en quatre. Ces cinq suites ne sont pas les cinq fragments que Nora devrait découper : un suffixe commence à sa position propre mais finit toujours à la borne cinq. La liste conserve le départ de chaque suite, et une demande portant sur un fragment plus court pourra ensuite s'arrêter avant cette borne commune. Aucun suffixe vide n'est ajouté aux cinq suites dans cette convention.
L'alphabet choisi range a avant b. La comparaison lit les lettres de gauche à droite ; une suite finie vient avant une suite plus longue qui commence exactement par elle. Camille range donc a, aba, ababa, ba, baba. Les départs associés deviennent quatre, deux, zéro, trois, un. Les trois suites commençant par a restent groupées, mais leurs départs sont en ordre décroissant dans ce groupe. Nora refuse de lire cette colonne comme une chronologie des tâches. Quatre est le départ du premier suffixe selon les lettres, pas le premier départ rencontré en avançant depuis le début de la bande.
Camille justifie les voisinages avant d'utiliser les rangs. a s'achève après sa première lettre tandis qu'aba continue ; aba s'achève après trois lettres tandis qu'ababa en garde deux autres. Entre ababa et ba, la première lettre suffit, a avant b. Enfin, ba s'achève avant baba. Dans la colonne des positions, aucune comparaison de petits nombres n'aurait produit cette suite de départs. Nora garde ensemble chaque suffixe et sa position d'origine. Si elle choisit plus tard le suffixe de rang deux, elle saura qu'il commence en zéro, au lieu d'appeler deux sa position dans le texte.
Le voisin précédent mesure ce qui était déjà apparu
Nora veut connaître les fragments distincts qui commencent à la position quatre. Le suffixe est a et possède un seul début non vide, a. C'est donc la première forme conservée. Au rang suivant, le suffixe aba possède les débuts a, ab et aba. Le premier est déjà connu depuis le suffixe a ; les deux suivants sont nouveaux. Camille inscrit le nombre un comme longueur commune entre les deux suffixes voisins, puis deux comme nombre de nouvelles formes ajoutées par aba. Elle n'ajoute pas trois simplement parce que le suffixe compte trois lettres : une lettre peut commencer plusieurs occurrences d'une même forme.
Le suffixe suivant ababa partage ses trois premières lettres avec aba. Ses débuts a, ab et aba étaient déjà présents ; il apporte seulement abab et ababa. Quand ba arrive ensuite, aucun caractère initial n'est commun avec ababa : b et ba sont nouveaux. Enfin, baba partage b et a avec ba, donc n'ajoute que bab et baba. Camille remet les cinq contributions un, deux, deux, deux et deux, soit neuf formes. Elle a utilisé les lettres partagées aux débuts des suffixes voisins, pas leurs fins communes. Les deux lettres ba à la fin d'ababa ne feraient pas commencer ce suffixe par b.
Les longueurs communes avec le voisin précédent sont zéro, un, trois, zéro et deux. Les cinq suffixes contiennent respectivement un, trois, cinq, deux et quatre lettres. Camille soustrait terme à terme pour obtenir ses contributions. Leur somme brute vaut quinze, comme un plus deux plus trois plus quatre plus cinq, mais six débuts sont retirés comme déjà vus. Le résultat neuf compte des formes de fragments non vides, tandis que quinze comptait les intervalles possibles de la bande. Nora conserve les deux nombres avec leur objet. Elle ne transforme pas six en six lettres effacées du texte : ce sont six débuts de suffixes qui auraient recopié une forme déjà inscrite.
Pourquoi regarder seulement le voisin précédent suffit-il ? Camille prend un début commun entre le suffixe actuel et un suffixe situé plus tôt dans l'ordre. Toutes les suites entre eux commencent nécessairement par ce même début : une première différence avant sa fin les placerait en dehors de l'intervalle. Le voisin immédiatement précédent le partage donc aussi. Réciproquement, tout début commun avec ce voisin a déjà été inscrit ou rencontré dans les suffixes précédents. La plus grande longueur déjà connue est ainsi exactement celle de ce voisin. Camille peut retirer tous les débuts jusqu'à cette longueur et conserver les plus longs, sans examiner une à une toutes les anciennes formes de sa feuille.
Elle complète la justification par la couverture des fragments. Tout fragment contigu de la bande possède un départ ; il est alors un début non vide du suffixe attaché à ce départ. Aucun fragment ne manque donc à l'ensemble des débuts des cinq suffixes. Le retrait des débuts déjà connus ne change pas cet ensemble, il supprime seulement leurs répétitions. Nora ne reçoit pas une liste de fragments fabriquée en concaténant les suffixes : ces suites se chevauchent dans la bande initiale et ne sont pas des morceaux à coller. La couverture s'appuie sur les départs existants, puis la suppression des copies s'appuie sur l'ordre des lettres.
Le rang d'une forme peut être remis sans prendre son rang pour un départ
Camille écrit les neuf formes dans l'ordre obtenu : a, ab, aba, abab, ababa, b, ba, bab, baba. Nora demande la cinquième, avec un rang compté à partir de un. Après la contribution du premier suffixe, une forme est passée ; après la seconde, trois ; après la troisième, cinq. La réponse se trouve donc parmi les deux nouveaux débuts d'ababa. Le premier a longueur quatre et occupe le rang quatre, le second longueur cinq et occupe le rang cinq. Camille remet ababa. La position de départ de ce fragment est zéro, même si son rang dans l'inventaire est cinq.
Cette lecture par contributions évite un autre résultat plausible mais faux. Le troisième suffixe rangé est ababa, mais ses cinq débuts ne doivent pas recevoir cinq rangs nouveaux à ce moment. Les trois plus courts ont déjà leurs rangs un, deux et trois. Si Nora repartait de quatre pour son premier début a, elle attribuerait des rangs supplémentaires à des formes déjà classées et déplacerait la cinquième réponse vers ab. Camille conserve donc à côté du suffixe sa longueur commune trois et les deux longueurs nouvelles quatre et cinq. Le rang d'une forme se reconstruit depuis ces longueurs, pas depuis la seule taille du suffixe qui la représente.
La longueur commune entre deux fins éloignées passe par les voisins intermédiaires
Nora compare maintenant a, de rang zéro, et ababa, de rang deux lorsque les rangs des suffixes commencent à zéro. Ils partagent seulement une lettre. Entre ces rangs, les longueurs communes voisines valent un puis trois ; leur minimum vaut un. Choisir leur maximum annoncerait trois lettres communes et ferait attribuer ba à la suite a qui s'est déjà terminée. Camille refuse ce maximum sur le texte rempli. Le suffixe intermédiaire aba partage davantage avec ababa qu'avec a, mais cette proximité d'un seul côté ne donne pas des lettres supplémentaires à l'autre extrémité de la comparaison.
Elle généralise ce contrôle dans la liste retenue. Si chaque paire de voisins entre deux rangs partage les k premières lettres, celles-ci passent identiques de voisin en voisin jusqu'aux deux extrémités. Les extrémités partagent donc au moins le minimum des longueurs voisines. Dans l'autre sens, si elles partageaient un début plus long que ce minimum, toutes les suites situées entre elles partageraient ce début, par leur ordre ; aucune paire voisine ne pourrait avoir une longueur commune plus petite. Les deux bornes donnent l'égalité. Camille remet ainsi le minimum sur une plage de voisinages pour retrouver une comparaison entre suffixes éloignés, plutôt qu'une moyenne de leurs ressemblances.
Un second contrôle oppose ababa, de rang deux, à baba, de rang quatre. Leurs premières lettres a et b diffèrent, donc la longueur commune vaut zéro. La plage de voisinages contient zéro puis deux et donne bien zéro. Les deux lettres communes entre ba et baba ne rendent pas les extrémités plus proches. Nora garde cette réalisation auprès de la première pour retirer une annotation « prendre la meilleure ressemblance trouvée entre les rangs ». Le renseignement pertinent est la plus petite longueur qui traverse tout l'intervalle. Cette réponse concerne le début exact des suffixes ; elle ne cherche pas un passage ressemblant à l'intérieur de chacun.
Une forme répétée peut utiliser les mêmes lettres dans ses deux occurrences
Le plus grand voisinage commun de la feuille vaut trois, entre aba et ababa. Il fournit le fragment aba aux départs deux et zéro. Nora contrôle les deux intervalles zéro à trois et deux à cinq, avec les bornes de fin exclues. Leur lettre de position deux appartient aux deux occurrences. La demande initiale autorise ce partage, donc Camille retient une répétition de longueur trois. Aucune répétition plus longue n'est possible : deux suffixes qui en porteraient une auraient un début commun plus long, et la règle de minimum entre leurs rangs obligerait un voisinage au moins aussi long dans la liste. Aucun des quatre voisinages n'atteint quatre.
Nora change alors la permission : les deux occurrences retenues ne doivent partager aucune position. aba ne passe plus. Ses départs zéro et deux sont séparés de deux, moins que sa longueur trois ; ses deux intervalles se rencontrent. Camille choisit ab, aux départs zéro et deux, avec les intervalles zéro à deux et deux à quatre. La borne deux appartient au deuxième intervalle mais pas au premier, puisque les fins sont exclues. Ces occurrences sont disjointes et atteignent longueur deux. La remise change réellement le fragment choisi ; elle ne garde pas aba en effaçant sa lettre partagée du relevé d'occurrences.
La preuve du nouveau maximum doit tester les distances des départs, et pas seulement l'ancien maximum trois. Les cinq suffixes offrent des paires de départs ; pour chaque paire, une longueur possible est bornée par leurs lettres communes et par la distance entre ces départs. La première borne assure les lettres identiques, la seconde empêche les deux intervalles de se croiser. Pour zéro et deux, les valeurs trois et deux donnent deux. Pour un et trois, baba et ba ont deux lettres communes et une distance deux, donc ba donne aussi une longueur deux. Les autres paires n'autorisent aucune longueur supérieure. Camille peut remettre ab ou ba selon une préférence ajoutée, mais ne les annonce pas comme une seule forme identique.
Nora retient ab pour cette feuille et garde ba comme autre optimum. Les deux noms de fragments portent chacun leurs départs. Une égalité de longueur deux ne signifie ni mêmes lettres ni mêmes intervalles : ab apparaît en zéro et deux, ba en un et trois. Camille ne mélange pas le premier départ de l'un et le second de l'autre pour fabriquer une paire de positions sous une seule forme. Les contrôles de distance avaient été faits à l'intérieur des paires de suffixes comparés, avec leurs débuts identiques. La liste des optima garde donc les deux réalisations complètes plutôt que deux longueurs isolées devenues interchangeables.
Chercher un début dans les suffixes garde les positions du texte
Une demande séparée cherche toutes les occurrences de aba. Dans la liste rangée, aba et ababa sont les seuls suffixes commençant par ces trois lettres ; ils occupent les rangs un et deux, avec trois comme borne de fin exclue. Leur colonne de départs donne deux puis zéro. Nora avait recopié un puis deux comme positions du fragment ; Camille lui montre que un était un rang, et que la bande y commence par b. Elle remet les positions deux et zéro dans l'ordre des suffixes, ou zéro puis deux si la consigne exige de parcourir le texte. Les lettres recherchées n'ont pas changé pendant cette conversion.
Le suffixe a se trouve juste avant cette plage. Il partage la première lettre du motif, mais s'achève avant la deuxième. Il ne porte donc aucune occurrence de aba. Le suffixe ba se trouve juste après, et diffère déjà à la première lettre. Camille conserve ces deux voisins comme contrôles de fermeture de la plage. Ils empêchent d'allonger la réponse vers tous les suffixes commençant par a ou vers un suffixe qui contiendrait a seulement plus tard. Chaque occurrence contiguë commence à son propre suffixe ; chercher son début n'autorise pas de déplacer sa première lettre après la position annoncée pour la faire convenir.
Une lettre remplacée peut changer l'ordre de plusieurs fins
Pour la dernière proposition, Nora remplace le b de position trois par c, avec l'alphabet a avant b avant c. La bande devient abaca. Les cinq suffixes sont maintenant abaca, baca, aca, ca et a. Leur ordre est a, abaca, aca, baca, ca, avec les départs quatre, zéro, deux, un, trois. Les suites aux départs zéro et deux contiennent le remplacement même si elles commencent avant lui ; leur ordre relatif s'inverse par rapport à ababa et aba. Camille ne modifie donc pas une seule ligne du classement au motif qu'une seule lettre du texte a changé.
Elle refait les quatre comparaisons voisines : a partage une lettre avec abaca, abaca une avec aca, aca aucune avec baca et baca aucune avec ca. La liste des longueurs devient zéro, un, un, zéro, zéro. Les tailles des suffixes dans cet ordre valent un, cinq, trois, quatre et deux ; leurs contributions nouvelles valent un, quatre, deux, quatre et deux. Le total est treize formes distinctes, contre neuf auparavant. Camille garde le nombre quinze d'intervalles possibles, inchangé par une substitution qui conserve cinq positions. Ce sont leurs textes qui sont devenus moins souvent identiques, pas le nombre d'intervalles disponibles dans la bande.
Nora demande de reprendre le fragment aba de la première recherche. Dans abaca, le suffixe de départ zéro commence encore par aba, même si sa quatrième lettre est maintenant c. Celui de départ deux commence par aca et ne convient plus. La réponse conserve donc zéro et retire deux. Camille refuse aussi un essai qui aurait retiré zéro parce que le suffixe complet avait changé : chercher un début de longueur trois ne demandait pas de garder les lettres qui le suivent. La correction modifie les formes distinctes et une occurrence du motif choisi ; elle ne supprime pas toutes les anciennes occurrences au seul motif que la bande a une version nouvelle.
Deux bandes séparées demandent un fragment commun, pas une répétition interne
Une dernière branche repart de la bande initiale ababa et reçoit une seconde bande baca. Nora veut le plus long fragment présent dans chacune. Elle ne demande plus deux occurrences dans ababa. Camille conserve deux séparateurs différents, # puis $, étrangers à l'alphabet des tâches, et forme la suite de travail ababa#baca$. Les lettres après # ont un autre propriétaire. Les séparateurs servent seulement à empêcher une comparaison de continuer au-delà des fins des deux bandes comme si les tâches appartenaient à une unique commande.
Camille associe à chaque suffixe son propriétaire avant de comparer les voisins. Parmi les voisinages qui joignent deux propriétaires différents, les longueurs communes valent un, un, un, zéro et deux. Le dernier compare le suffixe commençant au départ un de la première bande, baba, et celui commençant au départ zéro de la seconde, baca. Ils partagent ba, puis b diffère de c. Camille remet donc ba, avec les deux intervalles un à trois dans ababa et zéro à deux dans baca. L'ancien maximum aba de longueur trois concernait deux départs de la première bande ; il n'est pas disponible dans baca. Garder la liste des suffixes tout en ignorant les propriétaires aurait répondu à l'ancienne demande de répétition, et non à ce reçu de deux bandes.
Elle contrôle pourquoi aucun fragment commun plus long ne se cache entre des suffixes non voisins. Si un fragment de longueur k commence dans les deux bandes, tous les suffixes partageant ce début forment une plage du classement. Cette plage contient les deux propriétaires et aucun suffixe commençant par un séparateur. En passant d'un bout de la plage à l'autre, il existe donc deux voisins de propriétaires différents ; ils partagent au moins k lettres. Chercher le maximum de ces voisinages suffit ainsi pour les deux bandes. Les séparateurs différents interrompent une égalité lorsque les lettres communes atteignent une fin, sans fournir eux-mêmes une tâche supplémentaire. Le maximum deux est réalisé et certifié ; Camille ne reprend pas trois sous une nouvelle rubrique sans vérifier cette autre appartenance.
La dernière feuille conserve abaca, son ordre des suffixes et les treize formes obtenues. Les neuf formes de la première version restent attachées à ababa, avec la répétition aba lorsque le chevauchement était permis, puis ab lorsque deux intervalles disjoints étaient demandés. Les catégories de produits consultées ne sont pas des méthodes de recherche. Chaque réponse donne le texte, les positions et la permission qui permettent de refaire son contrôle, sans prendre le rang d'une fin pour un départ de tâche ni une longueur commune pour une autorisation de partager les mêmes lettres.