Léa écrit une bande fictive où a, b et c sont trois tâches créées pour la maison. Camille veut retrouver les portions contiguës qui portent les mêmes lettres de gauche à droite et de droite à gauche. La demande concerne des intervalles précis, pas la composition d'une phrase en miroir ni les gestes réellement effectués par quelqu'un. La première bande est abacaba, avec des positions numérotées de zéro à six. Une portion peut partager des positions avec une autre dans le premier relevé. Une autre commande demandera ensuite des morceaux disjoints qui couvrent une bande entière.
La notice 335100 du Met porte la catégorie des dessins.
La notice 335200 du Met porte également la catégorie des dessins.
La notice 335300 du Met porte la catégorie des estampes.
Ces catégories situent seulement les notices consultées. Aucun centre, alphabet, miroir ou calcul de découpe ne vient de leurs textes. Les images n'ont pas été examinées et aucune composition artistique n'est reprise.
Un centre peut porter plusieurs intervalles
Pour un centre placé sur une lettre, Léa appelle rayon le nombre de portions impaires emboîtées qu'elle peut conserver autour de cette lettre. Le rayon un garde seulement la lettre ; le rayon deux ajoute une lettre de chaque côté et donne une longueur trois ; le rayon trois donne une longueur cinq. Un rayon d correspond ainsi à une plus grande longueur deux fois d moins un. Pour les portions paires, le centre passe entre deux lettres : Léa enregistrera séparément leur nombre de paires extérieures identiques. Elle n'ajoute pas une lettre fictive au centre pour confondre les deux colonnes.
Au centre trois de abacaba se trouve c. Léa conserve c, puis aca, puis bacab, puis abacaba : quatre portions impaires, de longueurs un, trois, cinq et sept. Chacune reçoit son intervalle de début et de fin. Autour du b de position un, elle conserve b puis aba, mais ne peut étendre davantage parce que la bande s'achève à gauche. Le b de position cinq fournit également b puis aba avec d'autres départs. Léa ne compte pas ces deux aba comme une seule occurrence : l'un commence en zéro, l'autre en quatre. La même forme de trois lettres occupe deux places réellement distinctes dans ce relevé.
Les quatre centres restants, zéro, deux, quatre et six, portent chacun un seul a. Les rayons dans l'ordre des positions sont donc un, deux, un, quatre, un, deux, un. Leur somme vaut douze. Camille avait annoncé sept en recopiant le nombre de positions de la bande ; Léa lui fait retrouver les trois portions supplémentaires autour du centre c et les deux aba. Elle remet douze intervalles, y compris les sept lettres prises séparément. Le relevé n'exige pas qu'une position appartienne à une seule portion : plusieurs intervalles peuvent être emboîtés autour d'un centre ou partager des lettres entre des centres différents.
Un inventaire de formes distinctes donnerait pourtant sept réponses : a, b, c, aba, aca, bacab et abacaba. Léa obtient ce second inventaire en réunissant les textes identiques parmi les douze occurrences. Elle ne divise pas douze par un nombre de centres pour le trouver. a apparaît quatre fois, b deux fois et aba deux fois ; les quatre autres formes apparaissent chacune une fois. Camille choisit le relevé de douze intervalles pour la demande active et garde l'inventaire de sept formes sur une autre ligne. Les deux nombres résultent des mêmes lettres, mais l'objet compté n'est plus le même.
Une séparation centrale ne remplit pas la colonne des lettres centrales
Une autre bande, abba, met cette différence en évidence. Les quatre lettres prises seules ont chacune un rayon impair un. Aucun centre placé sur une lettre ne fournit une portion impaire plus longue. Entre les deux b, au contraire, Léa conserve d'abord bb, puis abba : deux portions paires emboîtées. Elle enregistre ce centre à la borne deux, juste avant la lettre de position deux. Le rayon pair vaut deux. Les autres bornes intérieures séparent a de b ou b de a et ont un rayon pair nul ; aucune paire de lettres extérieures identiques ne commence leur extension.
Le relevé total d'abba contient donc six occurrences : quatre lettres, bb et abba. Camille avait essayé de prendre le rayon impair du premier b et de lui donner la longueur deux ; cette conversion ne retrouve pas les mêmes partenaires. Pour bb, la lettre de position un doit rencontrer celle de position deux. Pour une portion impaire centrée sur la position un, cette lettre reste seule au centre, et les partenaires extérieurs seraient aux positions zéro et deux, a et b, qui diffèrent. Léa conserve deux colonnes de rayons avec leurs centres propres, au lieu de changer la formule de longueur sur une donnée qui portait une autre comparaison.
Chaque portion en miroir possède exactement un de ces centres : sa lettre centrale si sa longueur est impaire, sa séparation centrale si elle est paire. Raccourcir une portion en retirant une paire extérieure conserve ce centre et donne les portions emboîtées déjà comptées par son rayon. Léa peut donc sommer les deux colonnes sans compter deux fois le même intervalle. Le même texte, comme a, peut apparaître à plusieurs centres, mais ce sont alors plusieurs intervalles. La couverture du relevé ne dépend pas d'une reconnaissance de mots : elle vient des deux types de milieux et de l'égalité réellement testée sur leurs partenaires.
Une symétrie déjà contrôlée donne une limite à la copie
Léa veut éviter de recommencer toutes les comparaisons depuis un pour chaque centre. Elle conserve un intervalle impair déjà vérifié dont l'extrémité droite est la plus éloignée parmi celles traitées. Dans abacaba, le centre trois a fourni l'intervalle zéro à six, bornes incluses. Pour une autre position située dedans, elle peut regarder sa position réfléchie par ce grand centre. Les lettres du grand intervalle se correspondent exactement. Cette possibilité ne suffit cependant pas à copier tout rayon ancien : une partie du rayon réfléchi peut dépasser les lettres que le grand intervalle avait réellement contrôlées.
Au centre quatre de abacaba, la position réfléchie est deux. Son rayon vaut un. La place disponible jusqu'à l'extrémité droite six vaut trois en comptant la lettre centrale ; le rayon réfléchi un est strictement plus petit. Léa peut garder un exactement. Le premier échec autour du centre deux comparait b et c, aux positions un et trois ; sa réflexion compare c et b, aux positions trois et cinq, encore à l'intérieur du grand intervalle. La différence déjà connue se transporte donc avec les lettres. Aucune nouvelle comparaison au-delà de six n'est nécessaire pour décider que le centre quatre ne porte pas une portion impaire plus longue.
Elle conserve ici deux justifications, et pas un simple nombre copié. Les partenaires qui réussissaient avant l'échec se reflètent à l'intérieur de l'intervalle certifié ; ils demeurent identiques. La paire qui échouait s'y trouve aussi ; elle demeure différente après réflexion. Le rayon réfléchi est donc à la fois une longueur possible et une borne supérieure pour le nouveau centre. Si cette paire d'échec se trouvait en dehors du grand intervalle, la seconde justification manquerait. Léa n'étend pas la portée d'une symétrie locale aux lettres situées après son extrémité droite simplement parce que le centre nouveau est encore dedans.
La bande aaaab fournit précisément un cas où copier tout le rayon serait faux. Au moment de traiter le centre trois, Léa a contrôlé la portion aaa des positions un à trois, centrée en deux. Le centre réfléchi de trois est un, dont le rayon ancien vaut deux. Mais, depuis le centre trois, l'extrémité droite connue trois laisse seulement un comme rayon assuré. Copier deux annoncerait la portion aab, des positions deux à quatre, qui n'est pas en miroir. Léa prend d'abord un, puis compare réellement a en deux et b en quatre. L'échec laisse le rayon un, sans effacer le rayon deux qui appartenait à l'autre centre.
La frontière entre données connues et nouvelle lecture est donc visible dans ce refus. La lettre de position quatre n'était pas comprise dans l'intervalle aaa déjà certifié. La position zéro, qui avait servi au rayon deux du centre un, se refléterait justement vers cette position quatre ; la grande portion contrôlée ne permettait pas d'affirmer que leurs lettres étaient identiques. Léa retire la copie complète et garde la valeur limitée par l'extrémité droite. Elle ne modifie aucune lettre de aaaab pour sauver le résultat deux. Ce qui manquait à l'ancienne proposition était une comparaison hors du domaine déjà reconnu, et cette comparaison a maintenant échoué.
Atteindre une frontière ne dit pas ce qui se trouve après
Dans aaaaa, un autre essai conserve la portion aaa des positions zéro à deux, centrée en un. Quand Léa passe au centre deux, son reflet est zéro, de rayon un. La limite de l'intervalle connu donne également un. Cette égalité ne fournit pas un échec transportable : elle arrive exactement à la frontière droite deux. Léa compare donc les positions un et trois, toutes deux a, et étend le rayon à deux. Puis elle compare zéro et quatre, encore identiques, et atteint trois. Elle remet aaaaa autour du centre deux. Copier seulement un comme réponse finale aurait perdu deux portions réellement présentes, malgré une copie initiale correcte.
Léa garde les trois décisions auprès de leurs exemples : strictement à l'intérieur, le rayon réfléchi et son échec donnent une réponse exacte ; au-delà de la capacité de l'intervalle, la copie est tronquée ; à sa frontière, une extension réelle reste possible. Le cas de aaaaa n'autorise pas à prolonger aaaab sans comparaison, et le refus sur aaaab n'autorise pas à arrêter aaaaa avant sa paire extérieure. Les deux bandes fournissent des lettres différentes aux endroits précisément non couverts par l'ancienne reconnaissance. La limite conservée est un point de départ sûr pour la lecture, pas une promesse sur toutes les lettres suivantes.
Lorsqu'une extension atteint une nouvelle extrémité droite, Léa remplace l'intervalle de référence par cette portion effectivement contrôlée. Dans aaaaa, le nouveau centre deux donne zéro à quatre, qui avance la borne de deux positions. Dans abacaba, le centre quatre ne dépasse pas la borne six obtenue au centre trois : Léa conserve donc l'intervalle zéro à six, au lieu de le remplacer par la lettre seule de centre quatre. Le critère ne choisit pas le dernier centre traité ni le plus petit nom de tâche. Il garde l'extrémité droite la plus avancée, avec le centre qui rend sa réflexion utilisable pour les positions suivantes.
Le contrôle précédent décrit des comparaisons exactes sur une bande déjà donnée. Il ne mesure pas la vitesse d'un programme ni l'effort d'une personne. Son économie logique tient à la borne droite : les réussites d'extension qui demandent de nouvelles lettres la font avancer, tandis qu'un échec arrête la lecture du centre. Les positions dont le rayon réfléchi finit strictement à l'intérieur ne demandent aucune extension inconnue. Léa garde cette justification de la réutilisation auprès des tests, sans transformer les cinq lettres d'un exemple en certificat de durée d'exécution pour une grande bande ou pour un appareil réel.
Un centre présent dans une fenêtre peut porter une portion qui en sort
Camille demande maintenant seulement les miroirs entièrement contenus dans les positions un à cinq de abacaba, avec six comme fin exclue. Le texte retenu est bacab. Le centre trois est dedans et son rayon complet vaut quatre, mais la portion de longueur sept atteint les positions zéro et six, toutes deux en dehors de la fenêtre. Léa limite donc le rayon par les places disponibles à gauche et à droite : trois en comptant le centre, dans chaque direction. Le rayon conservé est trois et donne bacab, de longueur cinq. Filtrer seulement les centres compris dans la fenêtre aurait laissé passer abacaba sous une portée qu'il ne respecte pas.
Elle peut refaire ce contrôle sur n'importe quelle fenêtre déclarée sans recalculer les lettres de la bande. Pour une portion impaire de centre i dans l'intervalle de bornes l et r, fin exclue, le rayon admissible ne dépasse ni celui de la bande entière, ni i moins l plus un, ni r moins i. Leur minimum est réellement atteignable : c'est une portion emboîtée du miroir déjà vérifié et ses deux extrémités restent dans la fenêtre. Léa ne prend pas une moyenne de ces trois nombres ; une seule borne plus petite suffit à interdire un rayon plus grand. L'identité des lettres et l'inclusion des extrémités sont deux contrôles qui doivent réussir ensemble.
Le centre pair de bb dans abba demande les distances propres à sa séparation. Dans la fenêtre de borne un à trois, le centre passe en deux. Le rayon pair entier deux ne tient pas : il atteindrait zéro et trois, alors que les lettres permises sont seulement un et deux. Léa garde un et remet bb, de longueur deux. Elle n'ajoute pas un au nombre de places disponibles à gauche comme elle l'avait fait pour une lettre centrale impaire. La séparation n'est pas une lettre comprise dans le rayon. Les deux colonnes conduisent à des longueurs différentes parce qu'elles désignent des extrémités différentes, pas parce que bb aurait changé de texte.
La fenêtre un à six de abacaba conserve les rayons impairs des centres un à cinq limités à un, un, trois, un et un. Leur somme vaut sept occurrences, tandis que le maximum donne longueur cinq. Camille avait recopié ce maximum comme un nombre de portions ; Léa lui présente les cinq lettres seules, aca et bacab. Les deux demandes se séparent à nouveau : choisir la plus longue ou remettre tous les intervalles inclus. Le miroir aba centré en un et celui centré en cinq ne sont plus entièrement présents dans cette fenêtre, bien que leurs centres y soient. Le comptage utilise les rayons limités, pas seulement les douze occurrences de la bande entière dont on garderait les centres.
Une lettre ajoutée peut agrandir un ancien centre
Une branche distincte repart de aba, dont les rayons impairs valent un, deux et un. Nora lui ajoute b à droite et obtient abab. Le centre un conserve aba, mais le centre deux porte maintenant bab, de longueur trois : son rayon passe de un à deux. La lettre centrale a était déjà présente avant l'ajout. Léa ne peut donc garder tous les anciens rayons et calculer seulement celui de la nouvelle position trois. Elle vérifie les portions dont la frontière droite aurait pu être prolongée par la lettre ajoutée. La suite nouvelle fournit à l'ancien centre deux la paire b des positions un et trois, qui n'existait pas entièrement auparavant.
La feuille de comparaison peut conserver aba avec ses trois anciens rayons, puis abab avec un, deux, deux et un. Léa n'annonce pas que son simple parcours de centres sur une bande déjà donnée est devenu une procédure permettant de recevoir des lettres successives sans revoir les anciennes données. Les lettres de abab peuvent être traitées par le contrôle complet, qui fournit les nouveaux rayons exacts. Le droit de réutiliser une portion intérieure certifiée ne contient pas le droit de conserver un arrêt qui venait seulement d'une fin de bande. Cette limite reste distincte de l'échec par lettres différentes, comme celui a contre b sur aaaab.
Choisir de grandes portions ne suffit pas à couvrir la bande avec peu de morceaux
La dernière commande ouvre la bande aaba. Chaque morceau remis doit être en miroir, les morceaux doivent être contigus et disjoints, et leur réunion doit couvrir les quatre positions sans omission. Camille choisit d'abord le plus long miroir commençant en zéro : aa. Il reste ba, qui n'est pas en miroir ; elle le coupe en b puis a. La remise possède donc trois morceaux, aa, b, a. Léa trouve pourtant a puis aba, deux morceaux qui couvrent exactement la même bande. Choisir le plus long premier morceau n'avait pas donné le plus petit nombre de morceaux de la commande globale.
La seconde remise est minimale : aaba n'est pas lui-même en miroir, puisque ses partenaires intérieurs a et b diffèrent. Un seul morceau est donc impossible. Deux sont réalisés par les bornes zéro, un et quatre, qui donnent a puis aba. Le refus du premier choix ne porte pas sur aa : ces deux lettres sont identiques et demeurent un miroir correct. Il porte sur la conséquence de cette première coupure pour les lettres suivantes. Léa garde les trois morceaux du premier essai et les deux du second avec leurs bornes, au lieu de prétendre que le plus grand miroir local aurait été mal reconnu.
Pour garder ce raisonnement sur toute la bande, Léa inscrit le moindre nombre de morceaux pour chacun de ses préfixes. Le préfixe vide reçoit zéro. Une dernière portion en miroir allant de i à j peut suivre une meilleure couverture jusqu'à i et ajouter un morceau ; le moindre résultat parmi ces dernières portions donne la valeur jusqu'à j. Sur aaba, les valeurs aux cinq bornes sont zéro, un, un, deux et deux. Jusqu'à aa, le choix aa atteint un. Jusqu'à aab, aa puis b atteint deux. Pour les quatre lettres, la portion aba commençant en un peut suivre le premier a, déjà couvert en un morceau, et atteindre deux. La valeur de la borne deux ne contraint donc pas toute la remise à continuer depuis elle.
Chaque couverture valide possède une dernière portion qui commence à une de ces bornes et dont les lettres ont été vérifiées. Si sa partie précédente employait davantage de morceaux que la meilleure valeur connue à cette borne, Léa pourrait la remplacer par cette meilleure couverture sans changer la dernière portion ni introduire un chevauchement. Prendre le moindre coût de toutes les dernières portions ne perd donc aucune solution meilleure. Sur la feuille remplie, les rayons servent à décider quels intervalles sont autorisés ; les valeurs de couverture servent ensuite à choisir les coupures. Un maximum de rayon ne remplace ni ces valeurs ni les bornes qui reconstruisent les morceaux effectivement remis.
Léa remet les deux morceaux a et aba pour la dernière commande et conserve les relevés de douze occurrences sur abacaba, de six sur abba et de sept dans la fenêtre bacab. Les lettres n'ont pas été transformées en mots ou en objets observés pendant les contrôles. Les notices consultées ne fournissent aucune méthode de recherche ou de découpe. Chaque réponse reste attachée à sa bande, à ses centres et à la permission effectivement donnée : relever tous les miroirs, choisir le plus long contenu ou couvrir la bande entière avec peu de morceaux vérifiés.