Lycée Malherbe Année scolaire 2018-2019 MPSI - Informatique pour tous

TP no 6 - Chaı̂nes de caractères (Corrigé)

Nous avons déjà fait un TP sur les listes Python. Et de fait, les manipulations des listes et des chaı̂nes
de caractères sont très proches. Ce TP devrait donc avoir une saveur de déjà-vu !
Cependant, au fur et à mesure qu’on avance dans l’année, les programmes sont des plus en plus longs
et complexes : c’est normal !

1 Quelques commandes, déjà vues ou non

Une chaı̂ne de caractère est délimitée par des apostrophes ', des guillemets ", des triples apostrophes
''' ou des triples guillemets """. Les caractères peuvent être des lettres minuscules ou majuscules,
éventuellement accentuées, des symboles, etc. Accessoirement, l’espace est également considéré comme
un caractère.
Il y a aussi un caractère spécial noté \n qui correspond à un passage à la ligne.

1 Essayez de taper dans la console :

1 >>> s="Il fait\nbeau"
2 >>> s
3 >>> print(s)

1 >>> s="Il fait\nbeau"

2 >>> s
3 ’Il fait\nbeau’
4 >>> print(s)
5 Il fait
6 beau

2 Quel est le nombre de caractères de la chaı̂ne s ci-dessus ? Le vérifier avec la commande adéquate.

1 chaine="titi\ntoto"
2 print(len(chaine))
 

1 9
Le retour à la ligne est comptabilisé dans la longueur.

3 Créez les chaı̂nes s1="diplo" et s2="docus" et concaténez-les pour créer s3 qui devrait être un
dinosaure.

1 s1="diplo"
2 s2="docus"
3 s3=s1+s2
4 print(s3)
 

4 A partir de s3, comment obtenir simplement le caractère 'p' ?


1 chaine="titi"
2 print(chaine[1])
 

1
 5 Comment créer la sous-chaı̂ne 'lodoc' ?

1 s1="diplo"
2 s2="docus"
3 s3=s1+s2
4 print(s3)
5
6 print(s3[2])
7 print(s3[3:8])
 

6 La commande append fonctionne-t-elle avec les chaı̂nes de caractères ?

Non. . .
1 AttributeError: ’str’ object has no attribute ’append’
La plupart des commandes sur les chaı̂nes ont une syntaxe du type “méthode”, c’est-à-dire
chaine.commande(args) (rappelez-vous de append sur les listes).

7 Par exemple, créez une chaı̂ne s4 contenant le texte que vous souhaitez, puis tapez s4.upper() La
chaı̂ne s4 a-t-elle été modifiée par cette commande ?
s4 n’est pas modifiée, mais une chaı̂ne où toutes les minuscules ont été remplacées par des majuscules
est renvoyée.
En allant dans l’aide de str, vous trouverez d’autres commandes du même type. . .

2 Recherche de caractères

8 Créez une fonction caractere(M,c) prenant en entrée deux chaı̂nes de caractères, la chaı̂ne c étant
de longueur 1, et retournant True ou False selon que c est ou n’est pas un caractère de M.
Bien sûr, il suffit d’écrire c in M pour avoir la réponse. . . mais parcourez donc la chaı̂ne M “manuel-
lement” : ce TP est un entraı̂nement.
Je propose 3 solutions, comme pour le test de primalité dans le cours !

1 # version avec return
2 def caractere(M,c):
3 for x in M:
4 if c==x: return True
5 return False
6
7 # version avec un booléen et break
8 def caractere2(M,c):
9 trouve=False
10 for x in M:
11 if c==x: trouve=True; break
12 return trouve
13
14 # version avec un booléen et while
15 def caractere3(M,c):
16 trouve=False
17 i=0

2
18 while i<len(M) and not trouve:
19 if M[i]==c: trouve=True
20 i+=1
21 return trouve
22
23 print(caractere ("mathématiques","a"),caractere ("mathématiques","z"))
24 print(caractere2("mathématiques","a"),caractere2("mathématiques","z"))
25 print(caractere3("mathématiques","a"),caractere3("mathématiques","z"))
 

1 True False
2 True False
3 True False
Comprenez-vous bien pourquoi la version qui suit (sans le break) est moins performante (mais
néanmoins correcte) ?

1 def caractere_mauvais(M,c):
2 trouve=False
3 for x in M:
4 if c==x: trouve=True
5 return trouve
 

9 Créez une fonction positions_caractere(M,c) qui renvoie la liste des positions où on trouve le
caractère c dans M.
Par exemple, pour la chaı̂ne ornithorynquologie et la lettre o, on devra obtenir r0, 6, 12, 14s. Si le
caractère ne se trouve pas dans la chaı̂ne, on obtiendra une liste vide.
Un parcours par indices est nécessaire.

1 def positions_caractere(M,c):
2 pos=[]
3 for p in range(len(M)):
4 if M[p]==c:
5 pos.append(p)
6 return pos
7
8 # avec une liste définie en compréhension, c’est bien mieux!!!!
9 def positions_caractere2(M,c):
10 return [i for i in range(len(M)) if M[i]==c]
11
12 if __name__=="__main__":
13 print(positions_caractere("ornithorynquologie",’o’))
14 print(positions_caractere2("ornithorynquologie",’o’))
 

1 [0, 6, 12, 14]
2 [0, 6, 12, 14]

10 Créez une fonction compte_caractere(M,c) prenant en entrée deux chaı̂nes de caractères, la

chaı̂ne c étant de longueur 1, et retournant le nombre de fois où on trouve le caractère c dans M.
On pourrait bien renvoyer la longueur de la liste de la question précédente. . . faites plutôt un comp-
teur !

3
 11 ‹ Sauriez-vous utiliser la fonction sum pour répondre à la question précédente ?
Cette fois, plus besoin d’un parcours par indices. . .

1 def compte_caractere(M,c):
2 C=0
3 for x in M:
4 if x==c: C+=1
5 return C
6
7 # avec la fonction sum, c’est encore bien mieux!!!
8 def compte_caractere2(M,c):
9 return sum (1 for x in M if x==c )
10
11 if __name__=="__main__":
12 print(compte_caractere("ornithorynquologie",’o’))
13 print(compte_caractere2("ornithorynquologie",’o’))
 

1 4
2 4

3 Recherche de sous-chaı̂nes

12 Ecrire une fonction match(M,m,p) qui détermine si on peut lire le mot m en position p dans M.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Par exemple, dans le mot M “ on
a b c a e b c d a b c d a b c

0 1 2
peut lire le mot m “ en positions 5 et 9, mais nulle part ailleurs.
b c d
Bien sûr, il suffit d’écrire m==M[p:p+len(m)] (slicing) pour avoir la réponse. . . mais parcourez donc
la chaı̂ne m “manuellement” : ce TP est un entraı̂nement.

1 # version avec return
2 def match(M, m, p):
3 if p+len(m) > len(M):
4 return False
5 for i in range(len(m)):
6 if M[p+i] != m[i]:
7 return False
8 return True
9
10 # version avec un booléen et break
11 def match2(M, m, p):
12 if p+len(m) > len(M):
13 return False
14 res=True

4
15 for i in range(len(m)):
16 if M[p+i] != m[i]: res=False; break
17 return res
18
19 # version avec un booléen et while
20 def match3(M, m, p):
21 if p+len(m) > len(M):
22 return False
23 res=True
24 i=0
25 while i<len(m) and res:
26 if M[p+i] != m[i]: res=False
27 i+=1
28 return res
29
30 if __name__=="__main__":
31 M="pouettagadata"; m="tag"
32 print(match (M,m,5), match (M,m,6), match (M,m,11))
33 print(match2(M,m,5), match2(M,m,6), match2(M,m,11))
34 print(match3(M,m,5), match3(M,m,6), match3(M,m,11))
 

Remarque : on a pris garde à la fin de chaı̂ne. Mais avec m==M[p:p+len(m)], pas besoin de prendre
de précautions : le slicing s’arrête sans erreur en bout de chaı̂ne.
Comprenez-vous bien pourquoi la version qui suit (sans le break) est moins performante (mais
néanmoins correcte) ?

1 def match_mauvais(M, m, p):
2 if p+len(m) > len(M):
3 return False
4 test=True
5 for i in range(len(m)):
6 if M[p+i] != m[i]:
7 test=False
8 return test
 

Maintenant qu’on a la fonction match, on va pouvoir réécrire les fonctions de la section précédente
pour les sous-chaı̂nes, et non plus les caractères.

13 Ecrire une fonction sous_mot(M,m) prenant en entrée deux chaı̂nes de caractères, et retournant
True ou False selon que m est ou n’est pas un sous-mot de M (on dit aussi que m est un motif de M).
Avec l’exemple ci-dessus, la fonction renvoie True.
Bien sûr, il suffit d’écrire m in M pour avoir la réponse. . . mais parcourez donc la chaı̂ne M “manuel-
lement” : ce TP est un entraı̂nement.

1 from match import *
2
3 def sous_mot(M, m):
4 """Détermine si m est un sous-mot (facteur) de M"""
5 for p in range(1+len(M)-len(m)):
6 if match(M, m, p):
7 return True
8 return False

5
 9
10 if __name__=="__main__":
11 print(sous_mot("pouettagada","tag"))
12 print(sous_mot("pouettagada","plouf"))
 

On peut bien sûr écrire des versions avec booléens. . .

14 Ecrire une fonction positions_sous_mot(M,m) prenant en entrée deux chaı̂nes de caractères et

retournant la liste (éventuellement vide) de positions où on peut lire m dans M. Avec l’exemple ci-dessus,
la fonction renvoie [5,9].

1 from match import *
2
3 def positions_sous_mot(M, m):
4 """Détermine l’ensemble des positions dans M où on trouve le sous-mot (facteur)
m"""
5 pos = []
6 for p in range(1+len(M)-len(m)):
7 if match(M, m, p):
8 pos.append(p)
9 return pos
10
11 ### on pouvait aussi utiliser une liste définie en compréhension
12 ### élégant, n’est-ce pas?
13 def positions_sous_mot(M, m):
14 return [p for p in range(1+len(M)-len(m)) if match(M, m, p)]
15
16 if __name__=="__main__":
17 print(positions_sous_mot("pouettagada","tag"))
18 print(positions_sous_mot("pouettagada","plouf"))
19 print(positions_sous_mot("taratata","ta"))
 

15 Ecrire une fonction compte_sous_mot(M,m) prenant en entrée deux chaı̂nes de caractères et re-
tournant le nombre de positions où on peut lire m dans M. Avec l’exemple ci-dessus, la fonction renvoie 2.
On pourrait bien renvoyer la longueur de la liste de la question précédente. . . faites plutôt un comp-
teur !

16 ‹ Sauriez-vous utiliser la fonction sum pour répondre à la question précédente ?

Très classique : utilisation d’un compteur.

1 from match import *
2
3 def compte_sous_mot(M, m):
4 """Détermine le nombre de positions dans M où on trouve le sous-mot (facteur) m
"""
5 C=0
6 for p in range(1+len(M)-len(m)):
7 if match(M, m, p):
8 C+=1
9 return C
10

6
11 ### avec la fonction sum, c’est très élégant
12 def compte_sous_mot2(M, m):
13 return sum(1 for p in range(1+len(M)-len(m)) if match(M, m, p))
14
15 if __name__=="__main__":
16 print(compte_sous_mot("pouettagada","tag"))
17 print(compte_sous_mot("pouettagada","plouf"))
18 print(compte_sous_mot("taratata","ta"))
 

17 Les fonctions que vous avez écrites ne fonctionnent-elles pas aussi avec des listes ?
Tout fonctionne. Attention au in quand même. . .

1 from positions_caractere import *
2 from match import *
3 from sousmot import *
4 from positions_sousmot import *
5
6 L=[1,3,4,5,3,2,3,4,10]
7 print(positions(L,3))
8 print(match(L,[3,4],1))
9 print(match(L,[3,4],0))
10 print(sous_mot(L,[3,4]))
11 print(sous_mot(L,[2,4]))
12 print(positions_sous_mot(L,[3,4]))
13 print(positions_sous_mot(L,[2,4]))
 

3.1 Application
On donne le programme suivant.

1 from random import randint
2
3 nucleotides=’ATGC’
4
5 def caractere_aleatoire():
6 return nucleotides[randint(0,3)]
7
8 def chaine_aleatoire(n):
9 return ’’.join([caractere_aleatoire() for _ in range(n)])
10
11 if __name__=="__main__":
12 print(chaine_aleatoire(300))
 

18 Que fait la fonction chaine_aleatoire ?

Wikipedia nous apprend que l’ADN est constitué de quatre désoxyribonucléotides différents corres-
pondant à quatre bases azotées différentes :
— le dAMP, dont la base azotée est l’adénine (A), une purine,
— le dGMP, dont la base azotée est la guanine (G), une purine,
— le TMP, dont la base azotée est la thymine (T), une pyrimidine,
— le dCMP, dont la base azotée est la cytosine (C), une pyrimidine.

7
 Donc en fait, on créé un brin d’ADN aléatoire !

19 Réécrivez la fonction chaine_aleatoire “à la main”, sans utiliser la fonction join.


1 from random import randint
2
3 nucleotides=’ATGC’
4
5 def caractere_aleatoire():
6 return nucleotides[randint(0,3)]
7
8 def chaine_aleatoire(n):
9 return ’’.join([caractere_aleatoire() for _ in range(n)])
10
11 def chaine_aleatoire_new(n):
12 res=""
13 for _ in range(n):
14 res+=caractere_aleatoire()
15 return res
16
17 if __name__=="__main__":
18 from time import time
19 n=10**7
20 t=time()
21 chaine_aleatoire(n)
22 print("temps avec la commande join:\t\t",time()-t)
23 t=time()
24 chaine_aleatoire_new(n)
25 print("temps avec la nouvelle fonction:\t",time()-t)
 

1 temps avec la commande join: 14.028681993484497
2 temps avec la nouvelle fonction: 15.21896481513977
La fonction sans utiliser join prend un peu plus de temps, mais ce n’est pas flagrant.

20 Créez une chaı̂ne aléatoire m de longueur 5, et une deuxième M de longueur 104 . Déterminez le
nombre d’occurences de m dans M . Faites la moyenne sur une centaine d’exemples de M .
Pouvait-on prévoir ce résultat par un calcul de probabilités ?

1 from ADN import *
2 from compte_sousmot import *
3
4 nbessais=100
5 compteur=0
6 m=chaine_aleatoire(5)
7 for _ in range(nbessais):
8 M=chaine_aleatoire(10**4)
9 compteur+=compte_sous_mot(M,m)
10 print(compteur/nbessais)
 

1 9.58
Modélisons l’expérience. On suppose que m est fixé. L’univers est l’ensemble des mots de longueur 104

8
 possibles sur l’alphabet tA, T, G, Cu.
Cherchons l’espérance de la variable aléatoire X égale au nombre d’occurences de m dans M . No-
tons Ap l’événement : “on lit m à la position p dans M ” (fonction match). Alors
4 ´5
10ÿ 4 ´5
10ÿ
` ˘
E pXq “ E 1A p “ PpAp q.
p“0 p“0

A chacune de ces positions p, il y a 1 chance sur 45 “ 1024 de trouver m (car il y a 45 mots de longueur 5
sur un alphabet à 4 lettres).
1 1
Donc PpAi q “ 5 “ et
4 1024
104 ´ 4
E pXq “ « 9.76.
45
On vient de calculer l’espérance d’une variable aléatoire ! Elle se rapproche de la moyenne trouvée
expérimentalement. ˆ ˙
1
Attention : il serait faux d’affirmer que X suit une loi binomiale B 10 ´ 4, 5 , car les lectures
4
4
de m aux différentes positions ne sont pas indépendantes. Par exemple, si on lit le mot ATGCA en position
0, on ne pourra certainement pas le lire en position 1.

4 Pour terminer
4.1 Répétition d’un nucléotide
On reprend l’application de la section précédente.

21 ‹‹ Ecrire une fonction longueurA(M) qui renvoie la longueur de la plus longue sous-chaı̂ne de M
formée uniquement du nucléotide A.
Par exemple, longueurA(ACTAAACCCTTGGGATTACATGGGGAAGGTGTCGTAAAACGATTTTCAAC) renvoie 4.

1 from ADN import *
2
3 def longueurA(M):
4 i=0
5 record=0
6 while i<len(M):
7 if M[i]!="A":i+=1
8 else:
9 compteur=1
10 i+=1
11 while i<len(M) and M[i]=="A":
12 compteur+=1
13 i+=1
14 if compteur>record: record=compteur
15 i+=1
16 return record
17
18 M=chaine_aleatoire(50)
19 print(M,longueurA(M))
 

9
 22 ‹ ‹ ‹ Ecrire une fonction longueurATGC(M) qui renvoie la longueur de la plus longue sous-chaı̂ne
de M formée du même nucléotide (A, T , G ou C).
Par exemple, longueurATGC(CGAGTTCGCAGAAGTGTCCATATAAGATAGGCCGAGTTTTTCATCAGCGT) renvoie 5.


1 from ADN import *
2
3 def longueurATGC(M):
4 i=0
5 record=0
6 while i<len(M):
7 c=M[i]
8 compteur=1
9 i+=1
10 while i<len(M) and M[i]==c:
11 compteur+=1
12 i+=1
13 if compteur>record: record=compteur
14 return record
15
16 M=chaine_aleatoire(50000)
17 print(M,longueurATGC(M))
 

4.2 Jeux de mots (questions ouvertes)

A prendre comme un casse-tête de synthèse sur ce qu’on a fait jusqu’à présent.

23 ‹‹ Créez (et documentez) une fonction nombre_mots qui compte le nombre de mots de la chaı̂ne de
caractères. Par exemple, nombre_mots('Il fait très beau') devrait donner 4.
Vous pourrez notamment être attentifs : aux espaces répétés, aux signes de ponctuation, aux apos-
trophes. . .
Versions basiques, qui coupent aux espaces...

1 def nombre_mots(chaine):
2 compteur=0
3 for c in " "+chaine:
4 if c!=" " and oldc==" ":# un nouveau mot commence
5 # merci l’évaluation paresseuse pour le premier tour de boucle
6 compteur+=1
7 oldc=c
8 return(compteur)
9
10 def nombre_mots2(chaine):
11 compteur=0
12 n=len(chaine)
13 i=0
14 while i<n:
15 while i<n and chaine[i]==" ":
16 i+=1
17 if i<n:

10
18 compteur+=1 # début d’un nouveau mot
19 while i<n and chaine[i]!=" ":
20 i+=1
21 return(compteur)
22
23 machaine=" le lion est le roi des animaux et Simba est le roi des lions "
24 print("nombre de mots: ",nombre_mots(machaine))
25 print("nombre de mots: ",nombre_mots2(machaine))
 

Fonction trivialisée par la commande split :

1 def nombre_mots3(chaine):
2 return(len(chaine.split())) # split sans arguments coupe aux espaces
3
4 machaine=" le lion est le roi des animaux et Simba est le roi des lions "
5 print("nombre de mots: ",nombre_mots3(machaine))
 

24 ‹ ‹ ‹ Ecrire une fonction long_mot qui prend en argument une chaı̂ne de caractères et renvoie la
longueur du plus long mot du texte. On suppose que la chaı̂ne passée en argument est formée uniquement
de mots composés de lettres majuscules ou minuscules, séparés par un ou plusieurs espaces (pas de
ponctuation). Par exemple, en passant en argument la chaı̂ne

Le lion est le roi des animaux

la valeur renvoyée est 7 (“animaux” a 7 lettres).

Versions basiques, qui coupent aux espaces...

1 def longmot(chaine):
2 record=0
3 longueur=0
4 for c in " "+chaine+" ":
5 if c==" ": # un mot se termine
6 if longueur>record:
7 record=longueur
8 else:
9 if oldc==" ":
10 longueur=1
11 else:
12 longueur+=1
13 oldc=c
14 return record
15
16 def longmot2(chaine):
17 i=0
18 n=len(chaine)
19 record=0
20 while i<n:
21 while i<n and chaine[i]==" ":
22 i+=1
23 compteur=0
24 while i<n and chaine[i]!=" ":
25 i+=1

11
26 compteur+=1
27 if compteur>record:
28 record=compteur
29 return(record)
30
31 machaine=" le lion est le roi des animaux et Simba est le roi des lions "
32 print("longueur du plus long mot: ",longmot(machaine))
33 print("longueur du plus long mot: ",longmot(machaine))
 

Ou alors en anticipant :

1 def longmot3(chaine):
2 L=chaine.split() # split sans arguments coupe aux espaces
3 record=0
4 for mot in L:
5 if len(mot)>record:
6 record=len(mot)
7 return(record)
8
9 # ou encore plus rapide, en utilisant la fonction max
10 def longmot4(chaine):
11 L=chaine.split() # split sans arguments coupe aux espaces
12 return max([ len(m) for m in L ])
13
14 machaine="le lion est le roi des animaux et Simba est le roi des lions"
15 print("longueur du plus long mot: ",longmot3(machaine))
16 print("longueur du plus long mot: ",longmot4(machaine))
 

12