Après la rencontre, Nora compose une bande fictive d'étiquettes portant chacune une lettre A ou B. Camille doit relever des motifs sur cette bande, avec leurs positions de début et de fin. Aucun texte réel ni aucune machine d'impression n'est utilisé. La petite lecture sert à décider ce qui doit être conservé entre deux lettres, puis entre deux morceaux de bande reçus séparément. Il ne suffit pas de dire qu'un motif a été rencontré : plusieurs peuvent finir au même endroit.
Le catalogue contient quatre mots exacts : AB, ABA, BA et BAB. Chaque occurrence contiguë doit être relevée, y compris si elle partage des lettres avec une autre. Les positions commencent à un. Deux lettres séparées par d'autres lettres ne forment pas un motif contigu. La méthode classique de recherche simultanée par préfixes et suffixes n'est pas revendiquée comme une invention ; notre contrôle porte sur cette liste et sur les relevés effectivement obtenus.
Les trois pages consultées identifient des étiquettes. Aucune propriété d'impression ni méthode logicielle n'est adoptée ; catalogue, lettres et règles de repérage sont créés pour cette bande.
Brady présente des étiquettes : https://www.bradyid.com/ .
NIIMBOT présente des étiquettes : https://www.niimbot.com/ .
SheetLabels présente des étiquettes : https://www.sheetlabels.com/ .
Une bande de cinq lettres peut contenir sept occurrences
Nora remet ABABA. AB occupe les positions un à deux, puis trois à quatre. ABA occupe un à trois, puis trois à cinq. BA occupe deux à trois, puis quatre à cinq. BAB occupe deux à quatre. Camille obtient sept occurrences, attachées à quatre mots et à cinq positions de fin possibles. Elle ne transforme pas les deux ABA en un seul motif au seul titre que leurs lettres coïncident à la troisième position ; cette lettre participe à la fin du premier et au début du second.
À la troisième position, ABA et BA finissent ensemble. À la quatrième, AB et BAB finissent ensemble ; à la cinquième, ABA et BA encore. Une feuille qui annoncerait uniquement le mot le plus long à chaque position garderait AB en deux, ABA en trois, BAB en quatre et ABA en cinq : quatre événements, pas sept. Nora refuse ce relevé pour sa commande initiale. Elle conserve toutefois ces quatre mots comme résultat possible d'une autre consigne, « seulement le plus long à chaque fin », qui n'a pas été choisie ici.
Une autre proposition choisit AB aux deux premières lettres, puis reprend après leur fin. Elle trouverait encore AB aux positions trois et quatre, mais manquerait les mots passant par les lettres déjà utilisées. La commande n'avait pas exigé des portions disjointes. Les outils permettant de choisir des intervalles compatibles avaient déjà été traités ailleurs ; ils ne sont pas employés pour remplacer une recherche de toutes les occurrences. Nora garde ici les sept intervalles, sans décider lesquels seraient des étiquettes à découper matériellement.
Conserver une fin qui peut encore commencer un mot
Camille note les débuts possibles des mots du catalogue. Ils sont le début vide, A, B, AB, BA, ABA et BAB. Après un morceau de bande, elle conserve le plus long suffixe de ce morceau appartenant à cette liste de débuts. Un suffixe est une portion terminant le morceau ; un préfixe est une portion commençant l'un des mots. Leur rencontre conserve ce qui pourrait encore participer à une occurrence lors de la prochaine lettre, sans garder toute la bande dans le nom de cet état.
Après AB, elle garde l'état AB et annonce l'occurrence AB terminée. Si la lettre suivante est A, elle atteint ABA et annonce à la fois ABA et BA. Elle ne revient pas automatiquement au début vide après avoir annoncé AB. La même portion AB est un mot complet et le début d'un mot plus long, ABA. Effacer ce début au moment de la première annonce ferait manquer l'occurrence d'ABA aux positions un à trois. La réussite d'un premier mot ne met donc pas fin à toutes les recherches en cours.
L'état ABA illustre un retour qui ne consomme aucune lettre nouvelle. Le catalogue ne contient aucun début ABAB. Lorsque B arrive, Camille examine d'abord le suffixe BA d'ABA, qui est un autre début conservé ; y ajouter B produit BAB. Le nouvel état est donc BAB, pas le début vide. À la quatrième lettre de la bande, elle annonce BAB aux positions deux à quatre, ainsi que son suffixe AB aux positions trois à quatre. Le retour vers BA a gardé les deux lettres déjà présentes qui pouvaient réellement continuer, au lieu d'appeler le B reçu le premier signe d'une bande neuve.
Nora donne à Camille les retours à contrôler pour les deux longs états : ABA revient vers BA ; BAB vers AB. AB peut revenir vers B, et BA vers A. Ces retours portent sur des suffixes plus courts, ce qui empêche de tourner indéfiniment sur le même état lors d'une lettre impossible. Si AB reçoit B, ni AB plus B ni son suffixe B plus B ne constituent un début du catalogue. Le suffixe utile du morceau ABB est alors B. Camille conserve ce B ; elle n'annonce aucun mot, et une prochaine lettre A pourrait encore achever BA.
Ce dernier cas distingue l'absence d'annonce de l'absence d'information. Aucun des quatre mots ne finit en BB, mais la dernière lettre B peut commencer BA ou BAB. Nora corrige une case de son relevé qui avait marqué « aucun motif terminé, donc état vide ». Sur ABB suivi de A, le bon état B donne BA aux positions trois à quatre. L'état vidé à tort aurait conservé seulement A et manqué cette occurrence. Le relevé garde donc deux colonnes séparées : mots terminés par la lettre reçue et début encore utile après cette lettre.
Les fins courtes doivent suivre les longues
Pour chaque état, Camille prépare les mots du catalogue qui en sont des suffixes. AB annonce AB ; BA annonce BA ; ABA annonce ABA et BA ; BAB annonce BAB et AB. A, B et le début vide n'annoncent aucun mot. Cette liste de sorties concerne les mots effectivement présents dans le catalogue, pas tous les suffixes possibles des lettres. Le suffixe A d'ABA ne devient pas une occurrence déclarée, puisque A n'est pas un mot recherché.
Camille contrôle les sept annonces d'ABABA dans l'ordre d'arrivée. Après A, aucun mot. Après B, AB. Après A, ABA et BA. Après B, BAB et AB. Après A, ABA et BA. Chaque annonce reçoit sa fin présente, puis son début égal à cette fin moins la longueur du mot plus un. Ainsi, le BAB annoncé en quatre commence en deux, tandis que l'AB annoncé au même instant commence en trois. Nora ne copie pas le même début auprès de deux mots qui partagent une fin mais pas une longueur.
Si le catalogue contenait deux fois le même mot avec le même sens, cela ne fabriquerait pas deux occurrences différentes dans la bande. Notre catalogue ne contient aucune répétition, et nous cherchons des couples mot–positions, pas une multiplicité de lignes d'un fichier. Ce rappel ne fournit pas une nouvelle opération de repérage ; les questions de doublons de noms avaient déjà été remplies ailleurs. Les annonces multiples du cas présent viennent de mots différents réellement contenus dans le même suffixe.
Une coupure entre deux morceaux n'est pas un retour au début
Nora reçoit la bande en deux morceaux, AB puis ABA. Elle conserve leurs positions globales : le second commence en trois. Ces morceaux sont des transmissions séparées d'une seule bande, sans espace ni séparateur ajouté entre eux. Les occurrences qui traversent leur frontière restent donc demandées. Une autre commande qui placerait un vrai séparateur devrait au contraire l'annoncer explicitement et redéfinir les mots permis autour de cette coupure.
Après le premier morceau, Camille a annoncé AB de un à deux et garde l'état AB. Le A initial du second morceau donne donc immédiatement ABA de un à trois et BA de deux à trois. Son B suivant produit BAB de deux à quatre et AB de trois à quatre ; le dernier A fournit ABA de trois à cinq et BA de quatre à cinq. L'ensemble retrouve les sept occurrences de la bande reçue d'un seul tenant. Nora garde l'état et le numéro de position à la frontière : le nom AB sert à la continuation, tandis que le numéro deux permet de remettre les débuts globaux exacts.
Si elle remettait l'état au début vide avant le second morceau, elle obtiendrait seulement l'AB du premier, puis AB, ABA et BA dans le second : quatre occurrences. Les ABA et BA finissant en trois ainsi que le BAB finissant en quatre manqueraient. Nora conserve cette liste fautive avec ses omissions précises, plutôt qu'une formule vague disant que la coupure fait perdre « un peu de contexte ». Le second morceau n'était ni incorrect ni incomplet ; le défaut venait de l'état qu'elle lui avait donné au commencement de sa lecture.
À l'inverse, garder l'état AB ne demande pas d'annoncer une seconde fois l'AB déjà terminé au premier morceau. Les sorties sont émises quand une lettre nouvelle est consommée et conduit à un état qui les porte. L'état sauvegardé sert à décider l'effet de la prochaine lettre ; il n'est pas une instruction de répéter ses anciennes annonces lors de chaque reprise. Camille remet donc le relevé antérieur séparément de l'état de continuation. Une reprise sans nouvelle lettre ajoute zéro événement, même si l'état sauvegardé correspond à un mot complet.
Retirer un mot recherché ne retire pas forcément son début
Nora modifie le catalogue dans une branche neuve : BA n'est plus un mot recherché ; AB, ABA et BAB restent demandés. Camille ne peut pourtant pas effacer toutes les étapes portant BA. Cette portion demeure le début de BAB, et le retour d'ABA vers BA permet encore de rejoindre BAB lorsque B arrive. L'étape BA doit donc rester disponible pour lire, tout en perdant son annonce propre de mot terminé.
Sur ABABA, le nouveau relevé contient AB de un à deux, ABA de un à trois, AB de trois à quatre, BAB de deux à quatre, et ABA de trois à cinq : cinq occurrences. Les deux BA ont disparu parce que la commande les a retirées ; le BAB traversant les positions deux à quatre reste trouvé. Une suppression mécanique de l'étape BA aurait risqué de manquer ce BAB en effaçant le suffixe qui le prépare. Nora conserve la distinction entre un état servant de début et une marque indiquant qu'un mot exact est à annoncer.
Les cinq annonces appartiennent à cette nouvelle recherche, pas à une réécriture du relevé initial à sept. Les trois mots conservés gardent leurs positions, et les deux occurrences de BA restent des occurrences correctes sous l'ancien catalogue. Nora joint donc le catalogue à chaque relevé. Elle ne donne pas à une même commande une réponse qui perdrait ses anciennes annonces sans modification expressément reçue. Ce rappel sur l'historique reste court ; l'opération nouvelle porte sur le début BA nécessaire à BAB après retrait de son statut terminal.
Deux états peuvent avoir le même avenir sans avoir annoncé les mêmes mots
Camille souhaite alléger la fiche de continuation du catalogue initial à quatre mots. Elle compare AB à BAB. Dans les deux cas, un A nouveau conduit à ABA et émet ABA avec BA ; un B nouveau conduit à B et n'émet rien. Leurs réactions aux deux lettres possibles sont identiques. AB et BAB avaient pourtant annoncé des mots différents lors de leur arrivée : AB seul dans le premier cas, BAB et AB dans le second. Nora peut les réunir pour décider les seules annonces futures, mais pas pour reconstruire les annonces passées à partir du seul nom de l'état réuni.
Elle compare aussi BA à ABA. Un A nouveau mène dans les deux cas à A sans annonce ; un B nouveau mène à BAB et annonce BAB avec AB. Ces deux états peuvent donc former une seconde classe de continuation. Les autres états restent séparés : début vide, A et B. Camille obtient cinq classes en tout, au lieu des sept noms de débuts. Le regroupement garde les annonces sur les transitions, c'est-à-dire sur les lettres nouvellement lues. Il n'attribue pas à une classe une sortie immédiate unique qui remplacerait les sorties différentes de ses deux membres.
Nora donne un contrôle de cette réunion pour une suite de n'importe quelle longueur. Les deux membres de chaque classe produisent les mêmes annonces sur la prochaine lettre et arrivent dans la même classe suivante. Si leurs continuations restent identiques pendant les premières lettres, la lettre suivante retrouve donc encore les mêmes annonces et la même classe. On peut répéter ce raisonnement jusqu'au bout de toute suite finie. La fiche réduite ne repose pas seulement sur l'examen d'ABABA ; les deux réactions par classe suffisent à conserver toutes les annonces ultérieures, lorsque celles déjà produites ont été enregistrées avant la réunion.
Elle vérifie enfin qu'aucune réunion supplémentaire entre les cinq classes ne respecterait cette demande. Le début vide et A sont séparés par B : depuis A, AB serait annoncé ; depuis le début vide, rien. Le début vide et B sont séparés par A, qui annonce BA seulement depuis B. A et la classe BA–ABA sont séparés par B : AB seul contre BAB avec AB. B et la classe AB–BAB sont séparés par A : BA seul contre ABA avec BA. Les autres couples se contrôlent également avec A ou B en comparant leurs annonces ; les cinq réactions sont toutes distinctes sur au moins une de ces lettres. Nora garde donc cinq classes pour cette tâche précise.
Cette réduction ne donne aucun droit de remplacer le catalogue par cinq nouveaux mots. Une classe est un renseignement sur la continuation, pas une étiquette supplémentaire à rechercher. Nora conserve AB, ABA, BA et BAB comme les quatre noms des événements remis. Elle peut utiliser la fiche réduite à cinq classes pour retrouver ces événements, puis leur joindre leurs positions, sans transformer un nombre d'états en nombre d'occurrences ou en nombre de mots de la bande.
Une fenêtre récente demande aussi les débuts des événements
Une nouvelle commande demande uniquement les occurrences entièrement contenues dans les quatre dernières positions d'ABABA. La fenêtre est donc BABA, positions deux à cinq. Nora peut continuer à employer la même fiche pour détecter les fins, mais doit retirer du relevé les occurrences dont le début précède deux. L'état atteint après les cinq lettres ne porte pas à lui seul cette sélection temporelle.
Le relevé complet à sept perd AB de un à deux et ABA de un à trois. Il garde BA de deux à trois, BAB de deux à quatre, AB de trois à quatre, ABA de trois à cinq et BA de quatre à cinq : cinq occurrences. L'ABA finissant en trois n'est pas gardé au motif que sa fin appartient à la fenêtre ; son début un est dehors. Le BA finissant au même instant reste au contraire gardé, car son début deux appartient à la fenêtre. Nora teste donc chaque longueur auprès d'une même fin, sans attribuer à tous les mots annoncés simultanément le même statut d'inclusion.
Camille prépare une colonne du seuil de début permis et compare à ce seuil le début calculé de chaque événement. Lorsque la fenêtre avance, une ancienne occurrence peut quitter la liste sans qu'un nouveau mot soit annoncé à cet instant. La fiche de continuation et la liste des événements jouent donc des rôles différents. Sur ABA et sur ABABA, la continuation peut finir dans la même classe BA–ABA, tandis que les relevés complets comptent respectivement trois et sept occurrences. La classe ne doit pas servir de compteur rétrospectif. Nora garde le relevé de positions nécessaire à sa fenêtre, en plus du petit état qui lui permettra de lire une lettre suivante.
Les questions de suppression d'intervalles ou de conservation d'un registre avaient déjà été rencontrées dans d'autres jeux. Le contrôle développé ici est celui des mots simultanés de longueurs différentes : une même fin ne suffit pas à choisir ce qui appartient entièrement à la fenêtre. Le relevé remet les cinq événements effectivement gardés avec leurs débuts et leurs fins, puis précise quelle portion de la bande a été retenue.
Le catalogue et la portée du relevé restent attachés à la bande
Pour la bande entière et le catalogue initial, Nora remet sept événements. Pour la recherche sans BA, elle en remet cinq ; pour la fenêtre des quatre dernières positions avec le catalogue initial, elle en remet également cinq, mais avec une autre raison de sélection. La fiche de continuation accompagne les morceaux reçus sans répéter les annonces anciennes. Chaque relevé conserve les positions, le catalogue et la portée de la recherche effectivement demandée sur cette bande créée.