Recherche textuelle

illus

Source : Gilles Lassus

I. La méthode `find` de Python⚓︎

⌛ Avant de commencer

Vous devez travailler sur Basthon

Télécharger dans le même dossier :

🌐 Fichier pg798.txt : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 TD find_sujet.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Dans Basthon ouvrir find_sujet.ipynb, puis dans find_sujet.ipynb ouvrir pg798.txt (cliquer sur OK).

😀 La correction est arrivée ...

Télécharger dans le même dossier :

🌐 Fichier pg798.txt : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 Correction du TD find_corr.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Dans Basthon ouvrir find_corr.ipynb, puis dans find_corr.ipynb ouvrir pg798.txt (cliquer sur OK).

II. Recherche textuelle naïve⚓︎

Regarder les 5 premières minutes de la vidéo de l'introduction.

L'algorithme naïf et l'algorithme de Horspool en vidéo : Recherche textuelle

Illustration de l'algorithme

Auteur : Gilles Lassus

gif naif

Animation de Nicolas Revéret

Recherche naïve

Algorithme de recherche naïve

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=4-yr./oxpg2mcb1w937ve[ l,8+P5)ti]kné;ua(î_sh050g0C0M0U0N0F0Y0E0u0F0U0Y0Y0h010M0N0q010406050Y0T0t0t0U0l0k040e0o0F0T0@0o0Q050n0~1012140|0q04051k1d1n0n1k0|0g0N0B0,0.0:0=0Z0N0r0Z0F1B0Z0M0`050%0v0F0C1w0/0;011A1C1E1C0M1K1M1I0M0l1l0M0Z0,170Y0q0U0Q0=0s011O1y010b0)0C0Q0U0t0C1I1+1-1=1Q1^1M1{1}0`0a0E0J0l0o0q0o0Y0N1a0Q0E0#1)0l0l0C0u2i1d200Q1l0n1%2v1!1$1#1J0g220=1E0Q1`2f1I1t1v0-1P2F0N2H0Q0o2L1I0q2o1l2t2v2Z0}1,2j2N1?2S0l110F0`0E0w2s2%0{2$212)1Q2+2-2/0s2=1-2@2t2E012|0U2.040E0z302u0|332`0=36380E0i3c322%343i2/0K3m3e3o3g350o2,372/0d3t2^2(1x2{3y2}390A3D3f3G3h3I3A390H3M3v3O3x3z3j0y3U2_3W3q040w0c3#3F2O3X3J0w2;1e2?3u3$3.3(0w2 3?313^3-2*3Q380w3b3~3d3E3p430`0w3l473n3_423Y4c3s4f404a4j3)3C4f1o2X1d2L2y0g1$2D3w0u2T1~1l4w1m4u2#4s4C0#2Y3V3.0P0`0#0b3m493w0x2/4U3N3`0b0`2o0u0Z0C0l4)0C0X1{1u0C4Z4O1?0_040V4?4h2{0`0M0C0p504|411Q4_0G3m0E4V3%0`0t0o0@4T4s4!4^0`0L0f3,344X390E5s54340Y0g0`02030z0y0S5z5B5D5A5C5o3w5w2/5s0E2o0Q0B0o0N1N0.0E1E0Y502k0C0+2Q1t0u5#0E0V0R0B1`0M0T0C0F1M1}0Q0M0E0B0N0#0L5!0+0o0u0u0T2n1`5)0+0#5J3W5L5r5s2l5V4)0U0W2H0E5e5g2k1-0+6h0Z6j6l50520C0m6b3.6d5N0E5E5C6F5G5F3t6D5b3`0`5%0N68596M1?0o0`0h6S5j560`0D0O6K5N6T4~040N6Y4@1Q6V046X4f5a6Z0=0t0N0`3+4m6L6_014Q040x1A1M6.4}3h6O78550=6;020F0M0S6?2Z6^6/3h0v0`255u3w4_4{5i7n354 51537w79014_0L7c346;0j7H3w0Q7p047r7C7d7E0`7v2#710Q5d5f0N5h7W7x7F5n6 6D6)7X0`0P7L3W6;7k2?7m7D6{6}6(7,7_7S73751_7;6N047:6@6*7e5y7h0S842*7O7Q7%7D7u7s5c046n7#8l3.7F8e6:5q1-0g8t7a046w7B8i7S4_0D8q2*7b7R7I0`0I8H6+878D344_6%88717?7@317 3p7Z5g8O0=8F8(7y868+8T7*2Z067~7~898,8Q7^8^6;0I8Y2u8!3w7{3)7}7,8^738p8V7x7Y8-9a7D8X8y358g1`8.7U8+9c8o7$2?8^7)958?918m6P6R8K3w6;6z9A8m0U0q0q1`8x9E8r9m9L8I6,9l047G7+8@7.9Q9e7S8}8 398^933=8;8=7-7x732o5:0l1c9Y8#6,0Q5(5#3D0n4L0C2v2W9 4v1u4x2y2B2w0U1La20n4w0|ac0$0(0*04.

Version booléenne de l'algorithme de recherche naïve

Re-écrire l'algorithme précédent en s'arrêtant dès qu'une occurrence de motif est trouvée dans texte.

La fonction renverra uniquement un booléen.

Évaluations restantes : 5/5

.128013f6S=d-pg2mRâ 8P5)kuA_sh0:Fq4yr./oTxbc1w937ve[l,+tài]né;a(î050f0S0X0(0Z0U0w0n0L0U0(0w0w0e010X0Z0h010406050w0t0k0k0(0E0D040d0H0U0t0~0H0#0n020(0k0h0%0n0l0S180E0B0t0S0w050G1517191b130h04051G1z1J0G1G130f0Z0R0?0^0`0|0x0Z0i0x0U1X0x0X11050.0K0U0S1S0_0{011W1Y1!1Y0X1*1,1(0X0E1H0X0x0?1e0w0h0(0#0|0j011.1U010b0:0S0#1m0S1(24262b1:2e1,2h0k2j040a0n0p0E0H0h0H0w0Z1h1j0,220E0E0S0L2E1z2l0#1H0G202Q1}1 1~1)0f2n0|1!0#2g2B1(1P1R0@1/2!0Z2$0#0H2*1(0h2J1H2O2Q2{14251j2,2c2;0E180U110n0M2N2 122~2m311:3335370j3a263c2O2Z013h0(36040n0P3l2P133o3f0|3r3t0n0C3x3n2 3p3D370q3H3z3J3B3q0H343s370c3O3d301T3g3T3i3u0Q3Y3A3#3C3%3V3u0o3+3Q3-3S3U3E0O3?3e3^3L040M0y3}3!2-3_3(0M391A3b3P3~46400M3k4b3m4d45323/3t0M3w4j3y3Z3K4o110M3G4s3I4e4n3`4x3N4A1K2_1z2*2T0f1 2Y3R0L2=2t0+1Q1H2^0S2`3b3H054R0,4Z4C1:0s110,0b4#3,460N374:3@4f0b112J0L0x0S0E4~0S0v2h1Q530K0H1e4^4*0|10040)5b4m3g110X0S0J5l5h3p5e0V3H0n4u3R0#110k0H0~4/4H4;2c5e0r0z443p4?3u0n5N5p3R0w0f1102030P0O0%5U5W5Y5V5X5J5Q5S5M5N2J0#0R0H0Z1-0t1j581e0$2g0n2/1P1v260X0n0^0n2^0$0w2g0L1-0H0t0n2;2F0S5(3^5R375N620(0?0x0(0*2$0n5z5B0n0f260=634~6q6s5l5n0S0F6h466j5+1k5$5#5!5Z5%4A066l5u5E5j041}6b0R6g4A6V4_2c0H110e5t5v3^0s0L110A3s673O6U6/4f110Z6.6W0|6+046-6%6|2c0k0Z11436S6{71014,040N1W1,706)6X6 767f73020U0X0%752{6(5c3q0K112q5P3^5e5g5D7n3C5k5m5o7J7A5G7m7A730g7S5i3C7C047E7P7X017H7F6}046u0Z5C2}7f7R7q7K010H5L260f7W3p7_112;0X7}5w5k2y0t6#7*5F115I7d6U6l776X0s833^737x3b7z7%797b6`8e5O7f7h7j2f8j7+8i7?7T5T7u0%8z327Z7#7:7@7)7$3K5y5A7.891:7=7y8g727`0#7|8C7%5x6Y7N6$8L7Q110T8T7L047p8W7r110W8H8h8:7(110!8{726,8m3m8o8P7,8R7/4!7;8.8}8(8B8,7%5e0!8c2{6T8t8e8X3q119g8n9q8l919r049t959v8_9x8q418s8t9q7h8S8$979A2P963R8l949P9q0#8J2g8}8N9h977-9a3m9q5G9l4c9o9p7f8(6Z878+9u8^749x6;110I0E1w9H9/7@8(8?9^7@9w9M848=9x738`a93^9F4a9m7e7@7h2J0X0t0E0#9x9;86886S1z4%4Y4Iaz0G4L1z0X4NaE2W2R0(1+aB4L1F4)7%2J0k0v0b0(0s530x0P111r1t1v1x0n9,9)1M3c1G0u1g2J0n0w1e1g0Z1i0n1v0Z0na^1!67a~6sa?0E0~1-600Z0L0 5`6w1-630b1i2La_1j0i0E0m690n0(6c4$4S04anap1j9~a00Gay3u0Y6m621X6s4h6Ha,1O1Q3p1=1Z1#1%1 aK1,bN1#1@1$1`4T2U2X3p2#2%0w2)bM3Rb(2;2?4W4J2}8O5w4w3uai4c9Vb_0n4i9mb}4E3u4rc19:b~4zc6a3b~4Gca7A400n3Xawc7c30n3*cjcbcl3=cocfb~3|cs8%b_426I4D48b{4kc248c0b|ck48c5cIcp48c94!1M4JaC4VaEaGaF3payb+0Rb;azb?2}bB9J4-0S9(2P9q5L5ub@3 4{bu2K4 514 540/6#0v5^0U9Z117I9#aa6E7Od77G115saf7+9%d4045HcA1:c;8fc?6J5*6Q6O5Xdsdl0|6K6U5-5/5;b20nd25`1j5}0Z5 0#616365670#bo6b6da`0,dw01dy6l6A6p6r1-9%6w6ybE6Bd$0nd96GdWdY5Ndsd@6Na19V6~ac6,9E7a047caj8f8v118x7ldf32d|e91:7s8F9T3u9V9Xardp8a5f9e7M6Fdi0rd}047Vec7Y7D9Yel8Ud5eo985Bera*3y9.d{9zeteg9Qage0e29-9oc+7i7k9@9B9:9set7t7vasejdid69ba38QeFeA5d11esew7^8Z8#8@e-8)eqe:8~048/e a4etaee{cfe!e 9jeMeNeKdhfa9df3f9db469jeH129.akf8eLe@a8f78%fja68D04f6fy8pe0cDeIeTe58=c.eheZfsfv7~93e(eyekfkeme+9)fMfffUeBdjfn9nfpeO46am0-bw9{6=04byeXfG9IfMa5eYa7d~e@f4ft9De@ahd`fIbvaqf/6?6^f?3cbAbtaA2QaD2RaG2RaIbZgg4V13aC0-0/0;04.

Temps de recherches

⌛ Avant de commencer

Vous devez travailler sur Basthon

Télécharger dans le même dossier :

🌐 Fichier pg798.txt : "Clic droit", puis "Enregistrer la cible du lien sous"
🌐 TD temps_naif.ipynb : "Clic droit", puis "Enregistrer la cible du lien sous"

Dans Basthon ouvrir temps_naif.ipynb, puis dans temps_naif.ipynb ouvrir pg798.txt (cliquer sur OK).

III Le principe de l'algorithme Boyer Moore Horspool⚓︎

En bio-informatique

Les algorithmes de recherche textuelle sont aussi notamment utilisés en bio-informatique. C’est dans ce domaine que l’on va prendre les exemples du TP qui suivra.

Comme son nom l'indique, la bio-informatique est issue de la rencontre de l'informatique et de la biologie : la récolte des données en biologie a connu une très forte augmentation ces 30 dernières années. Pour analyser cette grande quantité de données de manière efficace, les scientifiques ont de plus en plus recourt au traitement automatique de l'information, c'est-à-dire à l'informatique.
Analyse de l'ADN : Comme vous le savez déjà, l'information génétique présente dans nos cellules est portée par les molécules d'ADN. Les molécules d'ADN sont, entre autres, composées de bases azotées ayant pour noms : Adénine (représenté par un A), Thymine (représenté par un T), Guanine (représenté par un G) et Cytosine (représenté par un C).

adn

Auteur du schéma : Victoria Denys/CEA sur https://www.cea.fr/comprendre/Pages/sante-sciences-du-vivant/l-ADN-dechiffrer-pour-mieux-comprendre-le-vivant.aspx?Type=Chapitre&numero=1

Algorithme de recherche naïve en partant à l'envers

Auteur : Gilles Lassus

gif naif inverse

Re-écrire l'algorithme de recherche naïve, mais en démarrant de la fin du motif et non du début. Certes, c'est pour l'instant très artificiel, mais cela va nous aider 😊.

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=4-yr./oxpg2mcb1w937ve[ l,8O+P5)ti]kn;ua(_sh050g0C0N0U0O0F0X0E0u0F0U0X0X0h010N0O0q010406050X0T0t0t0U0l0k040e0o0F0T0?0o0R050n0}0 11130{0q04051j1c1m0n1j0{0g0O0B0+0-0/0;0Y0O0r0Y0F1A0Y0N0_050$0v0F0C1v0.0:011z1B1D1B0N1J1L1H0N0l1k0N0Y0+160X0q0U0R0;0s011N1x010b0(0C0R0U0t0C1H1*1,1;1P1@1L1`1|0_0a0E0K0l0o0q0o0X0O190R0E0!1(0l0l0C0u2h1c1 0R1k0n1$2u1Z1#1!1I0g210;1D0R1_2e1H1s1u0,1O2E0O2G0R0o2K1H0q2n1k2s2u2Y0|1+2i2M1=2R0l100F0_0E0w2r2$0`2#202(1P2*2,2.0s2;1,2?2s2D012{0U2-040E0z2 2t0{322_0;35370E0i3b312$333h2.0L3l3d3n3f340o2+362.0d3s2@2%1w2`3x2|380A3C3e3F3g3H3z380H3L3u3N3w3y3i0y3T2^3V3p040w0c3!3E2N3W3I0w2:1d2=1n2W1c2K2x0g1#2C3v0u2S1}1k3`1l3^2!3=3005400!2X3U3-0Q0_0!0b3l3D330x2.4k3M3-0R0b0_1`0O0b0W1_0B0C0l0X4p4e1=0^040V4E3#4r0_0N0C0p4O4K3,4G0_0G3l0E4l3v0R0_0t0o0?4j482t4Z3V4H0M0f3s0E4?4Y4q2)0_2P1s0u0C4D4+384-3-0o0_0h4X534U040D0P4=4@592`4{584_1P550457514^4F1P0t0O0_3*51064@5q4L1=4g040x1z1L5j5r3g5i5p5g0;5m020F0N0S5o2Y5A4T2`0v0_244S334H4J515N344N4P4R5*5k0;4/5I5B5l0_0j5@5X3g5Z045#5:5J015(5$4!4$4(4w664.0_4:5e5z4?5+4#040Q5|335m5U2=5W3o5 612!5;640_5)6v636j4%4)6b3-5?625^5O5`6F1=5t0_3;5V6r3 0w0_030E0I2i1+0l0N2j1M0-0E1@2i0#0E1a6*0%6$1s5t0R0T4B0E6l5x6g5f6w5D5F1^6m676k743V5P0r5S6p306S3V6O045w5V5+0o4n041,0g774M044O4Q0C6M1P4H0D7w5K040O7q1=5m0J7E5h766I5}6x045d5M6w6o7c2t7e7r6D6a7L5%0_7z7Z756|6A6J7N0P4;6}6~6g6i0_7)6q7k567I7B7@7d7_045{7Q637g6Q2=5y7:5+5D7Y7j6w6j7}7U7 0h7T527R6L7%7f5u3(7A7N7.2Y877:6 6B4{0R4}4 8r5m0m8r6j0U0q0q1_7p8n6G6y8G5L7*7M6H8u8w7=7C7{016o8Z6j7D827+7G8Z846f7V5C0_2n0N0T0l1b8)7M8%8A0O4~508u1c4b0C2u2V943_1t3{2x2A2v0U1K970n3`0{9h0#0%0)04.

Le principe

L'idée est d'améliorer le code précédent (celui où l'on parcourt le motif à l'envers) en sautant directement au prochain endroit potentiellement valide.

Pour cela on regarde le caractère X du texte sur lequel on s'est arrêté (car X n'était pas égal au caractère de rang équivalent dans le motif):

Si X n'est pas dans le motif, il est inutile de se déplacer "de 1" : on retomberait tout de suite sur X, c'est du temps perdu. On se décale donc juste assez pour dépasser X, donc de la longueur du motif cherché. Si X est dans le motif (sauf à la dernière place du motif!), on va regarder la place de la dernière occurence de X dans le motif. On se décale afin de faire coïncider le X du motif et le X du texte.

Visualisation Boyer Moore Horspool par Nicolas Revéret

Boyer Moore Horspool

IV. Implémentation de l'algorithme Boyer Moore Horspool⚓︎

utiliser un prétraitement du motif pour déterminer les décalages

On va d'abord coder une fonction dico_lettres qui renvoie un dictionnaire associant à chaque lettre de mot (paramètre d'entrée) son dernier rang dans la variable mot. On exclut la dernière lettre, qui poserait un problème lors du décalage (on décalerait de 0...)

Dans l'exemple suivant :

Etape 0 :

étape 0

Le dictionnaire créé sera donc : dico = {"s": 0, "t": 1, "r": 2, "i": 3, "n": 4}

Etape 1 :

i prend la valeur 5 c'est à dire len(motif) - 1
"d" n'étant pas dans dico, on va faire un décalage de 6, c'est à dire de len(motif)

étape 1

Etape 2 :

i prend la valeur 5 + 6 c'est à dire de i + decalage
dico["n"] = 4, on va faire un décalage de 5 - 4, c'est à dire de len(motif) - 1 - dico["n"]

étape 2

Etape 3 :

i prend la valeur 11 + 1 c'est à dire de i + decalage
On a concordance pour la lettre "g", on vérifie la concordance des lettres en partant vers la gauche,
donc pour les indices i - k, k augmentant de 1 à chaque nouvelle comparaison. On observe qu'il n'y a plus concordance lorsque i - k = 8 .
"p" n'étant pas dans dico, on va faire un décalage de 6, c'est à dire len(motif) à partir de l'indice où l'on se trouve.
i prendra la valeur 8 + 6 = 14, c'est à dire que i prend la valeur i - k + len(motif)

étape 3

Etape 4 :

i prend la valeur 14
dico["s"] = 0, on va faire un décalage de 5 - 0 = 5, c'est à dire len(motif) - 1 - dico["s"]

étape 4

A vous de jouer : Implémenter l'algorithme Boyer Moore Horspool

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=4-yr./oxpBg2mcb1w937v{e[ l,8H+P5)ti]kn;ua(M}_sh050g0E0P0W0Q0H0#0G0v0H0W0#0#0h010P0Q0q010406050#0V0u0u0W0l0k040e0o0H0V0`0o0T050n111315170 0q04051n1g1q0n1n0 0g0Q0C0/0;0?0^0$0Q0s0$0H1E0$0P0}050*0w0H0E1z0=0@011D1F1H1F0P1N1P1L0P0l1o0P0$0/1a0#0q0W0T0^0t011R1B010b0,0E0T0W0u0E1L1.1:1^1T1{1P1~200}0a0G0M0l0o0q0o0#0Q1d0T0G0(1,0l0l0E0v2l1g230T1o0n1*2y1%1)1(1M0g250^1H0T1}2i1L1w1y0:1S2I0Q2K0T0o2O1L0q2r1o2w2y2$101/2m2Q1_2V0l140H0}0G0x2v2*0~2)242,1T2.2:2=0t2^1:2`2w2H012 0W2;040G0A332x0 362}0^393b0G0i3f352*373l2=0N3p3h3r3j380o2/3a2=0d3w2{2+1A2~3B303c0B3G3i3J3k3L3D3c0J3P3y3R3A3C3m0z3X2|3Z3t040x0c3(3I2R3!3M0x2@1h2_3x3)3;3+0x323_343{3:2-3T3b0x3e413g3H3s460}0x3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0x3%4G4k3K4s0t3.4M444O3M0t3^2$4q4x4D0t404Y4w3*4#492(1t2!1g2O2B0g1)2G3z0v2W211o4;1p4/4-2(4`0(2#4H1_0S0}0(0b3p4)3;0y2=5c4B2-0b590Q4`0!1P1Z2r0#5h561T0|040X5t4N3k0}0u0o0P5z4T0^5w0O0f3w0G5N0G5d2-593p5P5i1T0o0}0h5T5Q5v0}0D0Z5M5O5#0^58040b3B5!5V5B040Q5=5u0^0o5f5^1f4i5U5{380w0}0l1:0s0E5G375w5y4i5,640}286b3z6d6k3*5C5E6n3;5J5`5A015X040j6u5H010u0Q4f6r1_5J5L4p5O6L626v0T5S6f5?015w0F6G2~6p5F6R636U6W5@5_6!6v5w0R0R6A376x5Z616g6P5^5*5N6g5.2r0P0V0l602$6N6B6^0g3w4Z3Z5.5a6%015~5P6*755k040r0Y0K7d6m7h3s0}0P0E0p7t7o0}0I6/4x6Y0Q5b7q6l0}5K6`747r041w4`7A3Z6;7P3}5l5n5p1%0E5s7F3Z7p2(6S6^5D0`7E7%6#7H7J6@0}2T7N7Y7S1_7R6?6S6U6.6K5+7(7=7_5W5Y840^6D0}4R4Y6L6|0}0y1D1P8738837|636x020H0P0U6=736@65046j7!6s0}6e7-6O7s7u7w8z6H7/8m6v6x6z8L758w8y8D6B7$2_7;047*7D7x047I806M7K7B040S8j7{8u7(8R1}8#8C8W828Y5E8!8I5$8$8.0}8O8:63893,7J8d6S5.8g1|8j6^8-8P6:0}020s8r8t2_8*3Z968b9o6g5}0}1:779h8+7t7v6a8~5I0}6V9E8k6_9z7Q0}0L9e0}9g8T6c0}7 948M5Y9n349p7T8{7+8#9H9S8+9R8_7.040R6J73068)8)8X9-9!9u929Z2x9#1_964X3`9^a11T5.8}9W759Q91040h9 3c9}6y7da38#9=9o9@a681636^7?5m7^9I6x0m7d6^0W0q0q1}9y9+7#8BaB8laI8A908(ar8X6)ab9i040Laha7886E9761aq9_9a0}0E0-9DaN8J04ao42aras6va97,9t8`9B8Ha/8 9*9.8E9KaU3z6x9O9L9$9{2x6g6,8.5~2T9P7M5m0oan5Ta(a@a^acb5a|8n9NaY8v6i8?9I8V348X8Za{bD7}8Kb69Makbaa2a#a49|6S8Nbj7NbmbB9GaL04a~a.b38UbY9Iauaeb9bKbb8#6-989^8e04a,0#b$bH9/a=3gbq6MaSb,bx8;bz72b%9T5xbZbF8#0Obo99636}0)70c7bRat7=0T7@7Z4(0n530E2y2Zcv4:1x4=2B2E2z0W1Ocy0n4;0 cI0)0+0-04.

Algorithme de Boyer-Moore-Horspool

🐍 Script Python
def dico_lettres(mot):
    d = {}
    for i in range(len(mot)-1):
        d[mot[i]] = i
    return d

def BMH(texte, motif):
    dico = dico_lettres(motif)
    indices = []
    i = 0
    while i <= len(texte) - len(motif):
        k = len(motif)-1
        while k >= 0 and texte[i+k] == motif[k]: #(1)
            k -= 1
        if k == -1: #(2)
            indices.append(i)
            i += 1 #(3)
        else:
            if texte[i+k] in dico: #(4)
                i += len(motif) - dico[texte[i+k]] - 1 #(5)
            else:
                i += len(motif) #(6)

    return indices

On remonte le motif à l'envers, tant qu'il y a correspondance et qu'on n'est pas arrivés au début du motif
Si on est arrivés à la valeur k=-1, c'est qu'on a parcouru tout le mot : on l'a donc trouvé.
On a trouvé le motif, mais attention, il ne faut pas trop se décaler sinon on pourrait rater d'autres occurences du motif (pensez à la recherche du motif «mama» dans le mot «mamamamama»). On se décale donc de 1.
On s'est arrêté avant la fin, sur une lettre présente dans le mot : il va falloir faire un décalage intelligent.
On décale juste de ce qu'il faut pour mettre en correspondance les lettres.
La lettre n'est pas dans le motif : on se positionne juste après elle en se décalant de toute la longueur du motif.

Moins guidé : Implémenter l'algorithme Boyer Moore Horspool

Compléter ci-dessous :

Évaluations restantes : 5/5

.128013f06S:d=4-yr./oxpBg2mcb1w937v{e[ l,8H+P5)ti]kn;ua(M}_sh050g0E0P0W0Q0H0#0G0v0H0W0#0#0h010P0Q0q010406050#0V0u0u0W0l0k040e0o0H0V0`0o0T050n111315170 0q04051n1g1q0n1n0 0g0Q0C0/0;0?0^0$0Q0s0$0H1E0$0P0}050*0w0H0E1z0=0@011D1F1H1F0P1N1P1L0P0l1o0P0$0/1a0#0q0W0T0^0t011R1B010b0,0E0T0W0u0E1L1.1:1^1T1{1P1~200}0a0G0M0l0o0q0o0#0Q1d0T0G0(1,0l0l0E0v2l1g230T1o0n1*2y1%1)1(1M0g250^1H0T1}2i1L1w1y0:1S2I0Q2K0T0o2O1L0q2r1o2w2y2$101/2m2Q1_2V0l140H0}0G0x2v2*0~2)242,1T2.2:2=0t2^1:2`2w2H012 0W2;040G0A332x0 362}0^393b0G0i3f352*373l2=0N3p3h3r3j380o2/3a2=0d3w2{2+1A2~3B303c0B3G3i3J3k3L3D3c0J3P3y3R3A3C3m0z3X2|3Z3t040x0c3(3I2R3!3M0x2@1h2_3x3)3;3+0x323_343{3:2-3T3b0x3e413g3H3s460}0x3o4a3q3|453#4f3v4i434d4m3,3F4p4c3z3~3O4v3Q3}4e3,3W4A3Y4C4s0x3%4G4k3K4s0t3.4M444O3M0t3^2$4q4x4D0t404Y4w3*4#494(4B4l4V4h2(1t2!1g2O2B0g1)2G3z0v2W211o4_1p4@4=2(4 0(2#4H1_0S0}0(0b3p4)3;0y2=5h4.2~0b5e0Q4 0!1P1Z2r0#5m5b1T0|040X5y4N3k0}0u0o0P5E4T0^5B0O0f3w0G5S0G5i2-5e3p5U5n0^0o0}0h5Y5V5A0}0D0Z5R5T5*0^5d040b3B5)5!380}0Q5`5z5#5k042T5 5F380w0}0l1:0s0E5L375B5D4i5;670}286e3z6g6n3*5H5J6q3;5O655M015$040j6x370u0Q4f6u1_5O5Q4p5T6N5Z605|040g6I5+040F6U5G045I5K6i5{5B6X6%6Q0T5}6Y015B0R0R6D3z6A5(4i6P666-635/5S6j5?2r0P0V0l1f6{6j6~6T4p4Z3Z5?5f6/625U6+6}5p040r0Y0K6/6p7l6y6~0P0E0p7x7s0}0I6@6r6!5J0Q5g7u6f0}5P706|7v5q4 7E3;6_7T5W6S5r0o5t0)1%0E5x7K6o0}6h2(5{6~6#7I7B040O7O7a5}0T1w0v7(7W1T7V796(0}0F6?6M5:7/6.836Q822$7P6E6G044R4Y6N720}0y1D1P806Z5~8c666A020H0P0U6`8f7a68046m7*3Z7t7.6,0}7x7z6d8I6v7M8s6z0}6C8v7v8F8H8L668K2_7`7G0`7J8$6y6K7O8m8a040S8U8e2_8g4x8!1}7?7-8)8?7;8-926Q6w8Y376A8X8D5{6F6H886O8|7f8o8q8Q9d8M8@8_0}020s8A8C8{6j9f8j8_621:7c9o6}8N7y7A8R6J856/6~8u9F6y6A0L8U6~8^9K6V879Q9a5%9w349j3}6s8,7?6*8.3s0}9W9/7+040R6L8f069i9i8*9=9x5{8`9(9 9r6B8U9z4X3`9}9)5c5}95a48?a0ah8d9$a69c9666a97?9`8{9|ac899p2T7}7 9X5#0}0m9N0}0W0q0q1}9Eap8/7,aG6 aC6:8T9haw8*9Pa1al049%2xad2~8b9!6^0}9T993zar6{av9~5{5?0E0-9naN7L04at42awax665?7=a/7F8O9J9?8J9MaS9Oa6a.a+7Faj2x6j6;9B7{9U7R0oas5Ya?b2b37QaRbi7U5%bqbzaZ8wa-9U8~78bb8S5CaQ947?7^b7bBa7bS1_a;bA1_9bbD7}bsaS6)aQb9a|34bmbdbL7XaYakbG04bhbFbybk5a8%0}6=8;9}8n04a`0#b,bl84a c1b2aXa6a$3ccdbV81bHci3kbJ90bO7Hagc897aU9{bvc37476bKb`9:637|5raB4(0n580E2y2ZcK4^1x4`2B2E2z0W1OcN0n4_0 cX0)0+0-04.

V. Crédits⚓︎

Gilles LASSUS, Jean-Louis THIROT, Marine MERA et Mireille COILHAC

Recherche textuelle

I. La méthode find de Python⚓︎

II. Recherche textuelle naïve⚓︎

III Le principe de l'algorithme Boyer Moore Horspool⚓︎

IV. Implémentation de l'algorithme Boyer Moore Horspool⚓︎

V. Crédits⚓︎

I. La méthode `find` de Python⚓︎