Chaînes de caractères

1Chaines : structure, Unicode et methodes

s = "MPSI"
s[0]              # 'M'
s[0] = "X"        # TypeError: 'str' object does not support item assignment
s = "X" + s[1:]   # correct : on construit une nouvelle chaine, "XPSI"

Ecriture des litteraux

'simple'                  "double"          # equivalents
"l'apostrophe"            'le "guillemet"'  # choisir le delimiteur qui evite l'echappement
"""chaine
sur plusieurs lignes"""
"tabulation\tretour\nligne"                 # sequences d'echappement
r"C:\nouveau\dossier"                       # chaine BRUTE : \n n'est pas interprete

Unicode, ord et chr

Chaque caractere possede un point de code entier. Les fonctions ord et chr font la conversion dans les deux sens.

ord("A")      # 65        ord("a")  # 97
ord("0")      # 48        ord("é")  # 233
chr(66)       # 'B'
chr(ord("a") + 3)         # 'd'

def majuscule(c):
    """Version majuscule de c si c est une minuscule non accentuee."""
    if "a" <= c <= "z":
        return chr(ord(c) - 32)
    return c

Operations de base

s = "informatique"
len(s)              # 12
s[3]                # 'o'
s[-1]               # 'e'
s[0:5]              # 'infor'
s[::-1]             # 'euqitamrofni'
"a" in s            # True
s.count("i")        # 3
s.index("m")        # 4       (ValueError si absent)
s.find("z")         # -1      (pas d'exception)
"info" + "rmatique" # concatenation
"ab" * 3            # 'ababab'

Les methodes indispensables

s = "  MPSI  "
s.strip()          # renvoie 'MPSI' mais s est INCHANGEE
s = s.strip()      # il faut reaffecter

s = ""
for c in t:
    s += c          # MAUVAIS : Theta(n^2) au total

s = "".join(t)      # Theta(n)

2Algorithmes sur les chaines et chiffrement

Parcours d'une chaine

s = "MPSI"

for c in s:                      # par caractere
    print(c)

for i in range(len(s)):          # par indice
    print(i, s[i])

for i, c in enumerate(s):        # les deux
    print(i, c)

Algorithmes classiques

def compte_voyelles(s):
    """Nombre de voyelles (non accentuees) dans s."""
    c = 0
    for x in s.lower():
        if x in "aeiouy":
            c += 1
    return c

def est_palindrome(s):
    """s est-elle un palindrome, en ignorant casse et espaces ?"""
    t = [c.lower() for c in s if c.isalpha()]
    g, d = 0, len(t) - 1
    while g < d:
        if t[g] != t[d]:
            return False
        g += 1
        d -= 1
    return True

def frequences(s):
    """Dictionnaire lettre -> nombre d'occurrences."""
    f = {}
    for c in s.lower():
        if c.isalpha():
            f[c] = f.get(c, 0) + 1
    return f

def inverse_mots(phrase):
    """'le chat dort' -> 'dort chat le'."""
    return " ".join(phrase.split()[::-1])

assert compte_voyelles("Informatique") == 6
assert est_palindrome("Esope reste ici et se repose")
assert inverse_mots("le chat dort") == "dort chat le"

Recherche d'un motif

def recherche_naive(texte, motif):
    """Liste des positions d'apparition de motif dans texte. O(n*m)."""
    n, m = len(texte), len(motif)
    positions = []
    for i in range(n - m + 1):
        j = 0
        while j < m and texte[i+j] == motif[j]:
            j += 1
        if j == m:
            positions.append(i)
    return positions

assert recherche_naive("abababa", "aba") == [0, 2, 4]

Dans le pire des cas (texte "aaaa...a", motif "aaa...ab"), chaque position echoue au dernier caractere : \(\Theta((n-m+1)m)\) comparaisons. Les algorithmes de Knuth-Morris-Pratt ou de Boyer-Moore ramenent ce cout a \(\Theta(n+m)\) en exploitant l'information des comparaisons deja faites.

Chiffrement par decalage (chiffre de Cesar)

def cesar(s, k):
    """Chiffre s par decalage de k. Les caracteres non alphabetiques sont conserves."""
    res = []
    for c in s:
        if "a" <= c <= "z":
            res.append(chr((ord(c) - ord("a") + k) % 26 + ord("a")))
        elif "A" <= c <= "Z":
            res.append(chr((ord(c) - ord("A") + k) % 26 + ord("A")))
        else:
            res.append(c)
    return "".join(res)

assert cesar("abc xyz", 3) == "def abc"
assert cesar(cesar("Bonjour MPSI !", 7), -7) == "Bonjour MPSI !"

Le % 26 gere a la fois le retour au debut de l'alphabet et les decalages negatifs, grace au signe du modulo Python.

def casse_cesar(chiffre):
    """Affiche les 26 dechiffrements possibles."""
    for k in range(26):
        print(f"{k:2} : {cesar(chiffre, -k)}")

def casse_par_frequence(chiffre):
    """Retrouve la cle en supposant que la lettre la plus frequente code un 'e'."""
    f = frequences(chiffre)
    if not f:
        return 0
    plus_frequente = max(f, key=f.get)
    return (ord(plus_frequente) - ord("e")) % 26

3Cesar interactif, formatage et conversions

Formatage et affichage

nom, note = "Amine", 15.5
f"{nom} : {note}/20"              # 'Amine : 15.5/20'
f"{nom:<10}|"                     # aligne a gauche sur 10 colonnes
f"{nom:>10}|"                     # a droite
f"{nom:^10}|"                     # centre
f"{note:.1f}"                     # une decimale
f"{0.856:.1%}"                    # '85.6%'

# tableau aligne
eleves = [("Amine", 15.5), ("Sara", 18.0), ("Youssef", 12.25)]
print(f"{'Nom':<12}{'Note':>8}")
print("-" * 20)
for nom, n in eleves:
    print(f"{nom:<12}{n:>8.2f}")

Conversions chaine / nombre

int("42")           # 42
int("1010", 2)      # 10     : lecture en base 2
int("ff", 16)       # 255
float("3.14")       # 3.14
str(42)             # '42'
f"{255:b}"          # '11111111'
f"{255:x}"          # 'ff'

def vers_entier(s):
    """Convertit une chaine de chiffres en entier, sans utiliser int()."""
    n = 0
    for c in s:
        if not ("0" <= c <= "9"):
            raise ValueError(f"caractere invalide : {c!r}")
        n = n * 10 + (ord(c) - ord("0"))     # schema de Horner en base 10
    return n

assert vers_entier("2024") == 2024