TD11 : Palindromes, fonction témoin

Énoncé

1. Recherche de palindromes pairs

1.

prefpal(T):
  for i in range(len(T), 2):
    for j in range(i):
      compt = i
      while T[j] == T[i-j]:
        compt -=1

      if compt == 0:
        return i
prefpal2(T):
  for i in range(1, len(T)//2+1):
    flag = True
    for j in range(1,i+1):
      if T[j]!= T[2*i+1-j]:
        flag = False
        break
    if flag == True:
        return 2i

Complexité : on fait dans le pire des cas

\sum\limits_{i=1}^{\lfloor n/2 \rfloor} i = O(n^2)

opérations.

2.

Pour un mot $w$ et $k≤ \vert w \vert$ :

𝜋_w(k) ≝ \max \lbrace k' < k \mid P[1, k'] \text{ suffixe de } P[1, k]\rbrace

c’est le plus grand préfixe propre qui est un aussi un suffixe.

$T$ :

$a_1$ $a_2$ $a_3$ $a_4$   $⋯$
           

$\widetilde{T}$ :

$⋯$   $a_4$ $a_3$ $a_2$ $a_1$
           

Donc on considère T \# \widetilde{T} :

$a_1$ $a_2$ $a_3$ $a_4$   $⋯$ #   $⋯$   $a_4$ $a_3$ $a_2$ $a_1$
                           

tel que \# n’est pas une lettre de $T$.

Ainsi, si un mot de $P$ et un préfixe de T \# \widetilde{T} qui est aussi un suffixe, alors

\vert P \vert ≤ \vert T \vert

et en plus on sait que $P$ est un palindrome.

On pose W ≝ T \# \widetilde{T}

$𝜋_W(\vert W \vert)$ donne le plus grand préfixe de $T$ qui est un palindrome.

Remarquons que pour tout $n∈ℕ^\ast$ :

𝜋_W^n(\vert W \vert)

est toujours un préfixe suffixe de $W$.

On a même que $\lbrace 𝜋_W^m(\vert W \vert) \mid m∈ℕ\rbrace$ est l’ensemble des préfixes suffixes de $W$.

Donc le plus grand prefpal est

\max \lbrace 𝜋_W^m(\vert W \vert) \mid 𝜋_W^m(\vert W \vert) \mod 2 = 0 \rbrace = \min \lbrace m \mid 𝜋_W^m(\vert W \vert) \mod 2 = 0 \rbrace

Et le plus petit prefpal est

\min \lbrace 𝜋_W^m(\vert W \vert) \mid 𝜋_W^m(\vert W \vert) \mod 2 = 0 \rbrace = \max \lbrace m \mid 𝜋_W^m(\vert W \vert) \mod 2 = 0 \rbrace

car $𝜋$ est strictement décroissante jusqu’à atteindre $0$.

Complexité : $𝜋$ se calcule en $O(\vert W \vert)$ et le parcours des différentes valeurs est aussi en $O(\vert W \vert)$.

Il y a au plus $\vert W \vert$ valeurs que l’on voit et qui sont classées en ordre croissant

⟶ complexité en $O(\vert T \vert)$

3.

  $⋯$ $a_1$ $a_2$ $a_3$ $a_4$ $i$ $a_4$ $a_3$ $a_2$ $a_1$ $⋯$    
    $i+1-ray(i)$               $i+ray(i)$      

$P$ de longueur $2p$ est un prefpal ssi :

ray(p) = p

On en déduit que le plus petit prefpal est en position :

2 × \min \lbrace i \mid ray(i) = i \rbrace

4.

On veut maintenant calculer de manière efficace la fonction $ray$.

On suppose que $ray(i-k)≠ray(i)-k$

  • Cas 1 : $ray(i-k)<ray(i)-k$

    Mq $ray(i+k) = ray(i-k)$ :

    Schéma Cas 1

  • Cas 1 : $ray(i-k)<ray(i)-k$

    Mq $ray(i+k) = ray(i-k)$ :

    Schéma Cas 2

5.

Schéma Cas 3

6.

Voici l’algo :

i = 0
ray(i)=0
for j=1 to n//2:
  if j  i + ray(i):
    k = j-i
    if ray(i-k)  ray(i)-k:
      ray(j) = min(ray(i-k), ray(i)-k)
    else:
      k = ray(i)+i-j+1
      while k < min(n-j, j+1) and T[j+k] = T[j+1-k]:
        k+=1
      ray(j) = k-1
      if j == ray(j):
        return 2*j
      i = j
  else:
    k=1
    while k<min(n-j, j+1) and T[j+k]=T[j-k+1]:
      k+=1
    ray(j) = k-1
    if j == ray(j):
      return 2*j
    i=j

Dans cet algorithme, chaque lettre de mot est comparé au plus 2 fois.

Et on s’arrête dès qu’on trouve le plus petit prefpal.

7.

On double toutes les lettres.


2. Calcul d’une fonction témoin

8.

Pref(i) = \max \lbrace j \mid P[1,j] = P[i, i+j-1] \rbrace
tem(i) = 0 ⟺ Pref(i+1) = m-i \\ Pref(i+1) < m-i ⟺ tem(i) = Pref(i+1) + 1
if Pref(i+1)==m-i:
  tem(i)=0
else:
  tem(i) = Pref(i+1)+1

Algo en $O(\vert P \vert)$ car calcul de pref en $O(\vert P \vert)$.

9.

Par l’absurde, supposons que :

\begin{cases} T[i, i+m-1] = P \hspace{1em}⊛$ \\ T[j, j+m-1] = P \hspace{1em}⊛⊛$ \end{cases}

d’où

T[i, i+m-1] = T[j, j+m-1] \hspace{1em}⊛⊛⊛

Comme $i$ et $j$ sont incohérentes :

P[j-i + tem(j-i)] ≠ P[tem(j-i)]

Or :

\begin{align*} P[j-i+tem(j-i)] & = T[i-1+j-i+tem(j-i)] &&⊛ \\ & = T[i-1+j-i+tem(j-i)] &&⊛⊛⊛ \\ & = P[tem(j-i)] &&⊛⊛ \\ \end{align*}

absurde.

10.

Deux positions $1≤i<j≤n-m+1$ sont cohérentes si :

  • soit $j-i≥m$
  • soit $tem(j-i) = 0$

Soit $i<j$ cohérentes et $j<k$ cohérentes.

  • 1er Cas : Si $j-i≥m$ ou $k-j≥m$ alors $k-i ≥m$

  • 2ème Cas : Si $j-i<m$ et $k-j<m$ :

    Alors $tem(j-i)=0$ et $tem(k-j)=0$.

    Et :

    \begin{cases} ∀u∈⟦1, m-(j-i)⟧, P[j-i+u] = P[u] \\ ∀u∈⟦1, m-(k-j)⟧, P[k-j+u] = P[u] \text{ sinon} \end{cases}

    Soit $u∈⟦1, m-(k-i)⟧$

    P[(k-i)+u] = P[j-i + (k-j+u)] \\ = P[k-j+u] \\ = P[u]

    Donc $tem(k-i) = 0$

11.

Soit $i<j$ tq $i$ et $j$ sont incohérentes.

Remarque : quand deux positions sont incohérentes, on en enlève une.

Donc :

Invariant : à chaque début de boucle, touts les positions dans la pile sont cohérentes

On n’enlève jamais une position $i$ tq

T[i, i+m-1] = P

⟶ Si $i<j$ incohérentes et $T[j-1+tem(j-i)] ≠ P[tem(j-i)]$

Donc comme $0< tem(j-i)≤m-1$, on ne peut pas avoir

T[j, j+m-1] = P

⟶ Si $i<j$ incohérentes et $T[j-1+ tem(j-i)] = P[tem(j-i)]$

Supposons que $T[i, i+m-1]=P$ :

T[i-1+ tem(j-i)] = P[tem(j-i)] \\ ≠ P[j-i+tem(j-i)] \\ = T[i-1 + j-1 + tem(j-i)] \\ = T[j-1 + tem(j-i)] ≠ P[tem(j-i)]

contradiction.

Leave a Comment