Corrigé

On note $n_1$ et $n_2$ les longueur des chaines $S_1$ et $S_2$ respectivement.

Sous-séquence

algorithme sous_sequence(S1: chaîne, S2: chaîne) → booléen:
    i1 ← 0
    i2 ← 0
    tant que i1 < S1.longueur et i2 < S2.longueur:
        si S2[i2] == S1[i1]:
            i2 ← i2 + 1
        i1 ← i1 + 1

    rendre i2 == S2.longueur

Comme i1 augmente à chaque itération, la boucle va forcément s'arrêter ce qui finira l'algorithme.

Enfin l'algorithme fonctionne car i2 est incrémenté à la première occurrence possible.

Sa complexité est en $\mathcal{O}(\max(n_1, n_2))$. Cet algorithme est linéaire il est optimal.

Sous-mot

L'algorithme suivant regrade toutes les possibilités pour $S_2$ d'ˆ´tre un sous-mot de $S_1$. Il s'arrête à la première possibilité. Dans le pire des cas, il va effectuer $\mathcal{O}(n_1 \cdot n_2)$ opérations.

algorithme sous_mot(S1: chaîne, S2: chaîne) → booléen:
    
    pour chaque i1 de [0, S1.longueur[:
        i2 ← 0
        stop ← Faux
        tant que (stop == Faux) et (i2 < S2.longueur):
            si S2[i2] == S1[i1 + i2]:
                i2 ← i2 + 1
            sinon:
                stop ← Vrai
        
        si i2 == S2.longueur:
            rendre Vrai

    rendre Faux

Si tous les caractères de $S_2$ sont différents, il n'est pas nécessaire de tout recommencer. On peut utiliser l'optimisation suivante, qui donne la complexité voulue :

algorithme sous_mot(S1: chaîne, S2: chaîne) → booléen:
    i1 ← 0
    tant que i1 < S1.longueur:
        i2 ← 0        
        stop ← Faux
        tant que (stop == Faux) et (i2 < S2.longueur):
            si S2[i2] == S1[i1 + i2]:
                i2 ← i2 + 1
            sinon:
                stop ← Vrai
        
        si i2 == S2.longueur:
            rendre Vrai
        i1 ← i1 + i2

    rendre Faux

Permutation circulaire

La solution est optimale puisqu'elle est en $\mathcal{O}(n)$

algorithme permutation(S: [caractère], k: entier) → [caractère]:
    S2 ← un tableau de n caractères

    pour chaque i de [0, k [:
        S2[i] ← S[S.longueur-k + i]
    pour chaque i de [k, S.longueur[:
        S2[i] ← S[i-k]
    
    rendre S2

L'algorithme ci-dessus rend un tableau, il est donc facile de faire le décalage.

Si on droit qu'à un nombre constant de variables ceci n'est plus possible. Il faut ruser en utilisant des retournements

algorithme retournement(S: [caractère]) → ∅:
    pour chaque i de [0, S.longueur // 2[:
    S[i], S[S.longueur - 1 - i] ← S[S.longueur - 1 - i], S[i]

Comme $(A^R)^R = A$ et $(AB)^R = B^RA^R$, on a :

L'algorithme de permutation est alors tout simple :

algorithme permutation(S: [caractère], k: entier) → ∅:
    retournement(S[:-k])
    retournement(S[k:])
    retournement(S)

Et sa complexité est bien $\mathcal{O}(n-k) + \mathcal{O}(k) + \mathcal{O}(n) = \mathcal{O}(n)$.