TD10 : Recherche en espace constant et recombinaisons

M. SANGNIER

Énoncé

1. Recombinaison de mots

EX 1

On suppose que $\vert u \vert = \vert v \vert$

L’algo naïf ne marche pas.

Avec Simon, on cherche $u$ dans $v \cdot v$

EX 2

⟸ : immédiat

⟹ : si

au = u_1 u_2 u_3

et

av = u_1 \widetilde{u_2} u_3

alors :

  • si $u_1 = a u’_1$ (ou $v_1$) est non vide : on conclut, car

    u = u'_1 u_2 u_3 \sim u'_1 \widetilde{u_2} u_3 = v
  • si $u_1$ est vide :

    $au = u_2 u_3$ et $av = \widetilde{u_2} u_3$

    • Sous-Cas 1 : $u_2 = a$ : dans ce cas, on conclut
    • Sous-Cas 2 : sinon, $u_2 = a u’_2 a$, et :
    u = u'_2 a u_3 \\ v = \widetilde{u'_2} a u_3

    On en déduit que

    u \sim v

EX 3

On supprime toutes les lettres du début (si on peut enlever la même lettre au début), puis toutes les lettres à la fin (si on peut enlever la même lettre à la fin), et ce qui nous reste, c’est à vérifier que les deux mots restants sont miroirs l’un de l’autre.

L’algorithme est linéaire, avec 1).

EX 4

Si $u \sim \widetilde{v}$, alors

  • $u = u_1 u_2 u_3$
  • $v = \widetilde{u_3} u_2 \widetilde{u_1}$
\begin{align*} u & = u_1 u_2 u_3 \\ & ⟶^{\circlearrowleft} 𝜀 u_3 u_1 u_2 \\ & ⟶^{\sim} 𝜀 \widetilde{u_1} \widetilde{u_3} u_2 \\ & ⟶^{\circlearrowleft} \widetilde{u_3} u_2 \widetilde{u_1} = v \end{align*}

Donc

u \circlearrowleft\sim\circlearrowleft v

EX 5

Si $u \sim\circlearrowleft v$, alors il existe $w$ tel que :

  • $u = u_1 u_2 u_3$
  • $w = u_1 \widetilde{u_2} u_3 = v_1 v_2$
  • $v = v_2 v_1$

  • 1er Cas : $\vert v_1 \vert ≤ \vert u_1 \vert$ :

    u = v_1 x u_2 u_3 \\ \circlearrowleft x u_2 u_3 v_1 \\ \sim \underbrace{x \widetilde{u_2} u_3}_{=v_2} v_1 = v
  • 2e Cas : $\vert v_2 \vert ≤ \vert u_3 \vert$ : même raisonnement

  • 3e Cas :
$u_1$ $\widetilde{u_2}$   $u_3$  
  $v_1$   $v_2$  

$\widetilde{u_2} = \widetilde{u’‘_2} \widetilde{u’_2}$

Avec ce schéma, on a :

v = v_2 v_1 = \widetilde{u'_2} u_3 u_1 \widetilde{u''_2} \\ \widetilde{v} = u''_2 \widetilde{u_1} \widetilde{u_3} u'_2 \\ = u''_2 \widetilde{u_3 u_1} u'_2 \\ \sim = u''_2 u_3 u_1 u'_2 \\ \circlearrowleft u_1 u'_2 u''_2 u_3 = u_1 u_2 u_3 = u

Donc

u \circlearrowleft\sim v \text{ ou } u \circlearrowleft\sim \widetilde{v}

EX 6

u ≃ v ⟺ u \circlearrowleft\sim\circlearrowleft v

L’algo naïf est en $O(n^3)$, on teste toutes les rotations de $u$, et toutes les rotations de $v$ jusqu’à trouver une paire équivalente par $\sim$.


Si u ≃ v ⟺ u \circlearrowleft\sim\circlearrowleft v alors

u \circlearrowleft\sim v \text{ ou } u \circlearrowleft\sim \widetilde{v}

Réciproquement :

  • Si $u \circlearrowleft\sim v$, alors $u \circlearrowleft\sim\circlearrowleft v$ clairement

  • Si $u \circlearrowleft\sim \widetilde{v}$, alors (par 4)) $u \circlearrowleft\circlearrowleft\sim \circlearrowleft\widetilde{v}$, d’où $u \circlearrowleft\sim\circlearrowleft v$

Donc

u ≃ v ⟺ u \circlearrowleft\sim v \text{ ou } u \circlearrowleft\sim \widetilde{v}

On a un algo en $O(n^2)$ :

  1. On calcule $\widetilde{v}$
  2. Pour chaque rotation $u’$ de $u$, on teste $u’ \sim v$ et $u’ \sim \widetilde{v}$ (les deux en $O(n)$)

⟹ Au plus $2n^2 + n$ étapes.

2. Recherche en espace constant

2.1 Recherche d’un motif auto-maximal

Période $p$ d’un mot $w$ :

le plus petit entier strictement positif tel que w[1, \vert w \vert-p] = w[1+p, \vert w \vert]

EX 7

Soit $(𝛴 ≝ \lbrace a_i \rbrace_{i≥1}, ≤)$ un alphabet totalement ordonné.

Considérons le mot $a_1 a_2 a_1 a_1$ :

Soit $a_1 ≤ a_2$, soit $a_2 ≤ a_1$

  • Si $a_1 ≤ a_2$ : Le préfixe $a_1 a_2$ n’est pas automaximal ($a_1 a_2 ≤ a_2$) , donc $a_1 a_2 a_1 a_1$ non plus ($a_1 a_2 a_1 a_1 ≤ a_2 a_1 a_1$)
  • Si $a_1 ≥ a_2$ : alors $a_1 a_1 ≥ a_1 a_2$, et donc $a_1 a_1 ≥ a_1 a_2 a_1 a_1$, donc le mot n’est pas automaximal non plus.

EX 8

Si un prefixe $p$ de $w$ n’est pas automaximal (avec $w = pw’$), alors il existe un suffixe $s$ tel que

p = p' s

et $s>p$

Or :

s w' > p w' = w

et $sw’$ est un suffixe de $w$ donc

$w$ n’est pas automaximal.

EX 9

Pour un mot $w$ :

𝜋(k) ≝ \max \lbrace k' < k \mid w[1, k'] \text{ suffixe de } w[1, k] \rbrace
Period(w) = \vert w \vert - 𝜋(\vert w \vert)

On suppose que $p=Period(w[1, i-1])$ et $w[i] = a ≠ b = w[i-p]$.

|$w_1$|$b$|$w_1$|$a$|$w’$

  • |-|-|-|-

Montrons que $a<b$.

|$w_1$|$b$|$⋯$|$a$

  • |-|-|-

Comme tous les préfixes de $w$ sont automaximaux :

$w_1 b > w_1 a$

et on conclut


Soit $i∈⟦2,j⟧$, on va montrer que si

p = Period(w[1, i-1])

après exécution de la boucle au tour $i$ :

p = Period(w[1, i-1])
  • 1er Cas : si $w[i] = w[i-p]$

    alors $p = Period(w[1, i]) = Period(w[1, i-1])$

  • 2e Cas : si $w[i] ≠ w[i-p]$ : on veut montrer que dans ce cas,

    Period(w[1, i]) = i

    Soit $p’$ la période de $w[1,i]$ : suppososons que $p’<i$.

    Alors $p’$ est une période de $w[1,i-1]$, et donc

    p'≥p

    Soit $z$ un mot tq

    w[1,i] = zau

    et

    w[1,i] = vza

$T$ : texte $P$ : pattern

L = NULL
j = 0
for i from 1 to n
  while j > 0 and P[j+1]≠T[i] do
    j = j-Period(w[1,j])

  if P[j+1] = T[i]
    j = j+1
  if j = m
    Ajouter_liste(L, i-m)
    j = j-Period(w[1,j])
Period(w) = \vert w \vert - 𝜋(\vert w \vert)
Period(j) = j - 𝜋(j) \\ ⟹ 𝜋(j) = j - Period(j)
L = NULL
j = 0
p=1
for i from 1 to n
  while j > 0 and P[j+1]≠T[i] do
    j = j-p
  if j <p
    p = Period(w[1,j])

  if P[j+1] = T[i]
    j = j+1
    if (w[j]≠w[j-p])
      p = j
  if j = m
    Ajouter_liste(L, i-m)
    j = j-Period(w[1,j])

En espace constant : on n’a pas besoin de stocker $𝜋$.

Algo linéaire en complexité amortie (cf. la preuve pour $𝜋$).

Leave a comment