La partie I introduit le problème de la recherche de répétitions dans un texte et donne un premier algorithme permettant de le résoudre. La partie II est consacrée à la construction d'un mot infini sans carré. Enfin, les parties III et IV sont consacrées à la mise au point d'un algorithme efficace de détection de carrés.

La complexité, ou le coût, d'un programme

est le nombre d'opérations élémentaires (addition, soustraction, affectation, test, lecture ou écriture dans un tableau, etc...) nécessaires à l'exécution de

dans le cas le pire. Lorsque cette complexité dépend d'un ou plusieurs paramètres

, on dira que

a une complexité en

, s'il existe une constante

telle que, pour toutes les valeurs de

suffisamment grandes (c'est-àdire plus grandes qu'un certain seuil), pour toute instance du problème de paramètres

, la complexité de

est au plus

. Lorsqu'il est demandé de garantir une certaine complexité, le candidat devra justifier cette dernière.

On considère un alphabet

, c'est-à-dire un ensemble fini d'éléments appelés lettres. On appelle

l'ensemble de tous les mots de longueur finie utilisant les lettres de l'alphabet

. La longueur d'un mot

, c'est-à-dire le nombre de lettres qui le composent, est notée

. Le mot vide, de longueur 0 et noté

, appartient également à

. Le mot obtenu par concaténation de deux mots

, noté

, a pour longueur

et est composé des lettres de

, suivies des lettres de

Un carré est un mot égal à

où

est un mot non vide. On dit qu'un mot

contient un carré s'il existe un mot non vide

et deux mots (éventuellement vides)

tels que :

On dit alors que

est un carré de

. La période d'un carré

est la longueur du mot

. Par exemple, le mot bonbon est un carré de période 3 , et le mot repetition contient le carré titi de période 2.

On choisit de représenter les mots par des tableaux de caractères. Les cases d'un tableau de longueur

sont numérotées de 0 à

. Pour des raisons de cohérence entre les notations mathématiques et les représentations en machine, on note

les lettres qui composent le mot

. On a donc pour tout mot non vide

On dit aussi que

est la lettre qui apparaît à la position

du mot

. La numérotation des lettres d'un mot permet de parler de la position à laquelle un carré apparaît dans un mot. Par exemple, le mot tintinnabuler est représenté par le tableau décrit ci-dessous.

Numéro de la case	0	1	2	3	4	5	6	7	8	9	10	11	12
Caractère contenu dans la case

On dit que le mot (ou le tableau qui le représente) contient le carré tintin de période 3 , à la position 0 . En effet, la première lettre de tintin apparaît à la case 0 du tableau. Le mot contient aussi le carré

de période 1 , à la position 5 .

Le sujet de ce devoir s'appuie sur le langage informatique Caml Light. Le candidat pourra rédiger ses réponses dans ce langage, ou dans un format pseudo-code proche. On rappelle quelques fonctions Caml Light pour manipuler les tableaux.

vect_length m renvoie le nombre de cases du tableau m.
sub_vect m x y renvoie le sous-tableau de m constitué des y cases à partir de la case x .
make_vect renvoie un tableau de cases qui contiennent toutes la valeur .

(* Caml *) vect_length : 'a vect -> int
(* Caml *) sub_vect : 'a vect -> int -> int -> 'a vect
(* Caml *) make_vect : int -> 'a -> 'a vect

Partie I. Existence d'un carré

Question 1 On considère le programme suivant :

let carre_pe_pos m p i =
    let j = ref 0 in
        while !j < p &&
                i + !j + p < (vect_length m) &&
                m.(i + !j + p) = m.(i + !j)
        do
            j := !j + 1
        done;
        !j;;

(* Caml *) carre_pe_pos : char vect -> int -> int -> int

Donner les valeurs des appels suivants.

carre_pe_pos [|'c'; 'o'; 'u'; 'c'; 'o'; 'u' |] 3 0;;
carre_pe_pos [|'c'; 'o'; 'u'; 'c'; 'o'; 'o' |] 3 0;;
carre_pe_pos [|'a'; 'b'; 'a'; 'b'; 'a'; 'b'; 'a'; 'b' |] 2 4;;
carre_pe_pos [|'a'; 'b'; 'a'; 'b'; 'a'; 'b'; 'a'; 'b' |] 2 5;;

Question 2 On suppose

. Définir précisément ce que renvoie la fonction carre_pe_pos en fonction de ses arguments

. Que signifie le fait que la valeur renvoyée est égale à

Question 3 Écrire une fonction carre_pe qui prend en entrée un mot

et un entier

, et qui renvoie true si le mot

contient un carré de période

et false sinon.
(* Caml *) carre_pe : char vect -> int -> bool

Question 4 Écrire une fonction carre_naif qui prend en entrée un mot

et renvoie true si le mot contient un carré de longueur quelconque, et false sinon.
(* Caml *) carre_naif : char vect

bool

Question 5 Dans cette question, on suppose que pour l'alphabet considéré, pour tout entier

, il existe des mots de longueurs

sans carré. Donner alors la complexité dans le pire des cas de la fonction carre_naif définie précédemment.

Question 6 On considère l'alphabet

. Montrer que tout mot suffisamment long contient un carré. Donner un algorithme efficace (s'exécutant en temps constant) permettant de décider l'existence d'un carré pour les mots

construits sur l'alphabet

. On pourra supposer ici que la fonction vect_length s'exécute en temps constant.

Partie II. Construction d'un mot infini sans carré

Le but de cette partie est de construire un mot sur un alphabet de quatre lettres, de longueur infinie, et sans carré. La notion de carré s'étend naturellement aux mots infinis. Un mot infini est une suite de lettres indicées par les entiers de

. Le mot obtenu par concaténation d'un mot fini

et d'un mot infini

est le mot infini

composé des lettres de

, suivies des lettres de

. Dans ce contexte, un carré reste un mot fini de la forme

, avec

un mot non vide. Un mot infini

contient un carré s'il existe un mot fini non vide

, un mot fini

(éventuellement vide) et un mot infini

tels que

. Un bit est un nombre entier égal à 0 ou 1 . Soit

une suite de bits tous nuls à partir d'un certain rang (c'est-à-dire qu'il existe

tel que pour tout

). On dit que

est la représentation binaire d'un nombre entier naturel

On rappelle que tout nombre entier naturel possède une unique représentation binaire. On rappelle qu'en pratique, pour donner la représentation binaire d'un nombre entier dont les bits sont tous nuls à partir du rang

, on écrit simplement

Soit

un nombre entier naturel et

sa représentation binaire. On note

la profondeur de

, à savoir le plus petit entier

tel que

. On note

, le

-ème bit de la représentation binaire de

. On étudie le mot infini

sur l'alphabet

défini par

Question 7 Donner les huit premières lettres de

et vérifier que

contient des carrés de période 1 et 3 .

Question 8 Soient

deux nombres entiers. On définit

comme l'unique nombre entier de l'ensemble

égal à

modulo

. Soit

un nombre entier naturel. En comparant les représentations binaires de

et de

modulo

, montrer que

Question 9 Montrer que pour tous entiers

Question 10 Montrer que le mot

ne contient aucun carré de période

avec

.
Question 11 Généraliser le raisonnement précédent pour en déduire que le mot

ne contient aucun carré de période paire.

Question 12 Définir un alphabet sur quatre lettres et donner, sur cet alphabet, un mot infini, c'est-à-dire une suite de lettres indicée par les entiers de

, qui ne contient aucun carré.

Il existe également des mots infinis sur trois lettres sans carré, mais leur construction n'est pas demandée dans ce devoir. Dans la suite, on ne considère que des mots finis.

Partie III. Recherche efficace des carrés

Nous souhaitons mettre en place un algorithme efficace permettant la recherche de carrés dans un mot. Dans cette partie, nous nous intéressons à la détection de carrés créés lors de la concaténation de deux mots. Il s'en déduit un algorithme de test d'existence d'un carré dans un mot par la stratégie "diviser pour régner".

À titre d'exemple, considérons les mots

tin et

tinnabuler. Le carré tintin apparaissant au début du mot

est créé lors de la concaténation des mots

alors que le carré

apparaissant dans le mot

n'est pas créé lors de la concaténation de

et de

. Il apparaissait déjà dans le mot

Un mot

est un préfixe d'un mot

s'il existe un mot

tel que

. Un mot

est un suffixe d'un mot

s'il existe un mot

tel que

. Noter que le mot vide est préfixe et suffixe de n'importe quel mot.

Pour tous mots

sur un alphabet

et tout indice

tel que

, on définit :

est la longueur maximum d'un suffixe de qui apparaît dans en se terminant à la position de . Par exemple, lebon, dubonnet, 4 parce que le suffixe bon de lebon, de longueur 3, apparaît dans dubonnet et se termine à la position 4 de dubonnet.
est la longueur maximum d'un préfixe de qui apparaît dans en commençant à la position de . Par exemple, pabon, pabonpapa, 5 car le préfixe pa de pabon de longueur 2 apparaît à la position 5 de pabonpapa.

Question 13 On considère

. Soient

. Calculer

pour

compris entre 0 et 10 . Faites bien attention à lire correctement ce qui est demandé : pour

, on demande

, mais pour

, on demande

. Donner votre réponse en recopiant et complétant le tableau suivant.

Soient

deux mots. On appelle nouveau carré pour la concaténation de

, ou simplement nouveau carré quand il n'y a pas de risque de confusion, tout carré de

qui est la concaténation d'un suffixe non-vide de

et d'un préfixe non-vide de

(de manière plus imagée, le carré est à cheval sur les deux mots, ou est créé par la concaténation de

Un nouveau carré

qui apparaît en position

sur le mot

est un carré centré sur

lorsque

. Si

alors on dit qu'il est centré sur

. Par exemple, avec les mots

définis ci-dessus, cbabcbacbabcba est un nouveau carré de période 7 qui apparaît en position 4 sur le mot

. Il est centré sur

. On remarquera que si

, alors

est un nouveau carré qui n'est centré ni sur

, ni sur

Le schéma ci-dessous montre le cas général d'un nouveau carré obtenu lors de la concaténation de

et de

, centré sur

, de période

et se terminant à la position

Question 14 Dans l'hypothèse où il existe dans

un nouveau carré

centré sur

, de période

et se terminant à la position

, calculer en fonction de

l'indice

tel que :

Que peut-on dire des mots

?
Question 15 Montrer qu'il existe un carré de période

dans

se terminant à la position

et centré sur

si et seulement si
(a)

, et
(b)

, et
(c)

Question 16 Donner sans preuve une condition nécessaire et suffisante similaire à celle de la question précédente pour les carrés centrés sur

. On commencera par écrire le schéma montrant le cas général d'un nouveau carré centré sur

Question 17 Utiliser les résultats des questions précédentes pour donner les nouveaux carrés de période 7 centrés sur

obtenus lors de la concaténation de

Dans cette partie, on suppose donnée une implémentation des fonctions lms et

. En fait, pour des raisons d'efficacité du calcul, on ne dispose pas directement des fonctions lms et

, mais plutôt des fonctions suivantes :
(* Caml ) calcul_lms : char vect char vect int vect
( Caml *) calcul_lmp : char vect -> char vect -> int vect

La fonction calcul_lms appliquée à

renvoie un tableau d'entiers de taille

tel que l'entier stocké à la position

soit égal à

pour

. De façon similaire, la fonction calcul_lmp appliquée à

renvoie un tableau d'entiers de taille

tel que l'entier stocké à la position

soit égal à

pour

. On supposera que l'appel à chacune de ces fonctions sur les mots

a un coût

Question 18 Écrire une fonction nouveau_carre_v qui prend en entrée deux mots

et renvoie true si le mot obtenu lors de la concaténation de

et de

fait apparaître un nouveau carré centré sur

, et false sinon. On garantira une complexité en

.
(* Caml *) nouveau_carre_v : char vect

char vect

bool

On admettra l'existence d'une fonction nouveau_carre_u (similaire à celle de la question précédente) de complexité

qui renvoie true si un nouveau carré centré sur

apparaît lors de la concaténation des mots

(et renvoie false sinon).

Question 19 Écrire une fonction nouveau_carre qui prend en entrée deux mots

et renvoie true si un nouveau carré apparaît lors de la concaténation des mots

, et renvoie false sinon. On veillera à bien prendre en compte d'éventuels nouveaux carrés qui ne sont ni centrés sur

ni centrés sur

, et on garantira une complexité en

.
(* Caml *) nouveau_carre : char vect

char vect

bool

Question 20 En déduire une fonction carre qui renvoie true si le mot

donné en entrée admet un carré, et false sinon. On garantira que le calcul se fait en

.
(* Caml *) carre : char vect -> bool

Partie IV. Implémentation efficace des fonctions lms et

On souhaite maintenant implémenter efficacement le calcul de

, et

. Comme annoncé dans la partie précédente, on implémente la fonction calcul_lms (respectivement calcul_lmp) qui, appliquée à

, renvoie un tableau d'entiers de taille

tel que l'entier stocké dans la case

est égal à

(respectivement

) pour

. On souhaite de plus garantir une complexité

lors de l'appel à calcul_lms u v (respectivement calcul_lmp u v).

Pour programmer calcul_lmp, on met à jour itérativement la table des préfixes d'un mot comme expliqué ci-après. Considérons un mot

et pour tout entier

, posons

Une méthode naïve pour calculer pre

consisterait à évaluer chaque valeur indépendamment des valeurs précédentes par comparaisons directes. Cependant, l'utilisation des valeurs déjà calculées permet d'obtenir un algorithme plus efficace.

Illustrons le procédé sur un exemple. Considérons le mot

, et supposons

déjà connu pour

allant de 0 à 3 comme indiqué dans la table des préfixes donnée ci-dessous.

	0	1	2	3	4	5	6	7	8	9

pref	10	1	0	5

Table 1 - Table des préfixes pour le mot

Posons

. Le calcul de

nous dit que

est un préfixe de

(et c'est le plus long débutant à la position 3). Autrement dit,

On souhaite calculer pref . De l'égalité précédente, on déduit . Dans la mesure où , la situation à la position 4 est semblable à celle de la position 1 . On a donc . De même, on a .
On regarde maintenant comment calculer pref . Du calcul de pref , on a préfixe de , et donc les égalités suivantes : , et . De plus, on a vu que . On en déduit que .
Enfin, regardons comment calculer . On a suffixe de et préfixe de et donc de (car ). On en déduit que . Pour savoir la longueur maximale du préfixe de qui démarre à la position 7 , il nous faut donc reprendre les comparaisons : contre contre On obtient ici pref .

Pour faire ce raisonnement de façon systématique, on introduit, l'indice

étant fixé, deux valeurs

qui constituent les éléments clés de la méthode. Elles satisfont les relations :

Question 21 Compléter la table 1 en indiquant la valeur de

et les valeurs possibles de

pour chaque indice

compris entre 2 et

Question 22 Soient

pref

, et

pref

.
a. Que peut-on dire du mot

?
b. Lorsque que

, exprimer

en fonction de

Question 23 Soient

pref

, et

pref

. On suppose de plus que

. Montrer le résultat suivant :

où

est la longueur du plus long préfixe commun à

. Autrement dit, on a

. On posera

, et on étudiera séparément les cas

, et

. Ces trois cas correspondent aux trois situations illustrées au travers des exemples donnés en début de cette partie.

Question 24 On considère le code donné en Figure 1.

let calcul_pref v =
    let pref = make_vect (vect_length v) 0 in
    pref.(0) <- vect_length v;
    let g = ref 0 in
    let f = ref 0 in
        for i = 1 to vect_length v - 1 do
            if i < !g && pref.(i - !f) < !g - i then
                pref.(i) <- pref.(i - !f)
            else
                if i < !g && pref.(i - !f) > !g - i then
                    pref.(i) <- !g - i
                else
                begin
                    f:=i;
                    g:= max !g i;
                    while !g < vect_length v && v.(!g) == v.(!g - !f) do
                        g := !g + 1;
                    done;
                    pref.(i) <- !g - !f;
                end;
        done;
        pref;;

Figure 1 - Code de la question 24.

(* Caml *) calcul_pref : char vect -> int vect

a. Justifier que ce code réalise bien le calcul demandé, c'est-à-dire que la fonction calcul_pref, appliquée à un mot

, renvoie le tableau pref défini ci-dessus.
b. Justifier la terminaison de l'algorithme. Donner et justifier sa complexité.

Dans les trois questions suivantes, on demande des programmes courts et simples. En particulier, dans les deux questions suivantes, l'idée est d'utiliser la fonction calcul_pref sur des mots facilement obtenus à partir de

et d'un caractère spécial '#' n'appartenant pas à l'alphabet (on pourra utiliser des concaténations et des retournements).

Question 25 Donner une implémentation de complexité

pour la fonction calcul_lmp.

Question 26 Afin d'implémenter la fonction calcul_lms demandée à la question suivante, on se propose tout d'abord de programmer une fonction calcul_suff, telle que (calcul_suff v) renvoie la table des suffixes du mot v , c'est-à-dire un tableau d'entiers de taille

tel que l'entier stocké dans la case

est égal à

. Écrire le code de la fonction calcul_suff v en garantissant une complexité

. Attention, ici, on ne suppose pas disposer d'une implémentation
de la fonction calcul_lms car cette fonction sera implémentée à la question suivante à l'aide de calcul_suff.
(* Caml *) calcul_suff : char vect -> int vect

Question 27 En utilisant la fonction calcul_suff de la question précédente, écrire le code de la fonction calcul_lms. On garantira une complexité en

.
(* Caml *) calcul_lms : char vect -> char vect -> int vect

Notes : Il existe de nombreuses constructions de mots infinis sans carrés. Le plus ancien est le mot de Thue. Le mot présenté dans ce sujet est original, mais très proche du mot de Dean [R.A. Dean, A sequence without repeats on

, American Mathematical Monthly, volume 72, pages 383-385, 1965]. L'algorithme présenté de ce sujet est dû à Main et Lorentz [M.G. Main and R.J. Lorentz, An

algorithm for finding all repetitions in a string, Journal of Algorithm, volume 5, pages 422-432, 1984].