repl.it
@fduffaud/

Boyer-Moore-animation1

Tkinter

No description

fork
loading
Files
  • main.py
  • nohup.out
main.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
from tkinter import *
import tkinter.font as tkFont


def calculR(m, A):
    R = {}
    for c in A:
        R[c] = -1
    for c in m:
        R[c] = m.rfind(c)

    return R


def suivant():
    global bougerMotif
    if bougerMotif == True:
        deplacerMotif()
        bougerMotif = False
    else:
        explorerMotif()


def explorerMotif():
    global i, j, bougerMotif

    # Ne pas calculer une nouvelle valeur de i si i a ateint la valeur max len(t) - len(m)
    if i < len(t) - len(m):
        # Les cases du texte ou du motif temporairement coloriées sont remiese dans leur état par défaut
        for case in l_cases_temp:
            case.set_etat_contour(NORMALB)
            case.set_etat_texte(NORMALB)
        # On vide l_cases_temp
        l_cases_temp.clear()
        # Tant que le motif correspond au texte et que j >= 0, on décrémente j pour regarder le caractère à gauche
        if (j >= 0) and (t[i + j] == m[j]):
            # On met en vert le caractère t[i+j] et on enregistre le caractère t[i+j] dans la liste des caractères de t à mettre en mode normal pour la position suivante du motif
            casesTexte[i + j].set_etat_contour(BON)
            casesTexte[i + j].set_etat_texte(BON)
            l_cases_temp_match.append(casesTexte[i + j])
            # On passe à la case à gauche
            j = j - 1
            # On remet toutes les cases d'indice j dans leur état normal
            for k in range(len(m)):
                casesIndexJ[k].set_etat_contour(NORMALW)
            if j >= 0:
                # On met en rouge le contour de la case j si j >= 0
                casesIndexJ[j].set_etat_contour(ETUDIE)

        elif j < 0:
            # On a trouvé un motif: on enregistre son index
            l_index_motifs.append(i)
            # On dessine en vert tous les éléments de t qui matchent le motif (contour et texte
            for k in range(i, i + len(m)):
                casesTexte[k].set_etat_contour(BON)
                casesTexte[k].set_etat_texte(BON)
                l_cases_trouvees.append(casesTexte[k])

            # On vide la liste des bonnes cases du texte stockée temporairement
            l_cases_temp_match.clear()
            # On recherche le motif à la position suivante
            i = i + 1
            # On a trouvé un motif: il faut bouger celui-ci
            bougerMotif = True

        else:
            # On ajoute toutes les cases de l_cases_temp_match à la liste l_cases_temp
            while l_cases_temp_match != []:
                case = l_cases_temp_match.pop()
                l_cases_temp.append(case)

            # On met en rouge le caractère t[i+j] et on enregistre le caractère t[i+j] dans la liste des caractères de t à mettre en mode normal pour la position suivante du motif
            casesTexte[i + j].set_etat_contour(ETUDIE)
            casesTexte[i + j].set_etat_texte(ETUDIE)
            l_cases_temp_t_droite.append(casesTexte[i + j])
            # Les caractères de m[j] et t[i+j] ne sont pas identiques
            car = t[i + j]
            # Si le mauvais caractère ne fait pas partie de m, on décale le motif après le mauvais caractère
            if R[car] == -1:
                i = i + j + 1

            else:
                # On met en rouge le caractère d'indice R[car] du motif
                casesMotif[R[car]].set_etat_contour(ETUDIE)
                casesMotif[R[car]].set_etat_texte(ETUDIE)
                l_cases_temp_droite.append(casesMotif[R[car]])
                # On déplace le motif au minimum de 1 (pas à gérer le cas j-R[c] < 0)
                i = i + max(1, j - R[car])

            # On a pas trouvé le motif et m[j] != t[i+j]: il faut bouger le motif
            bougerMotif = True


def deplacerMotif():
    global i, j

    if i <= len(t) - len(m):
        # On se place à la fin du motif
        j = len(m) - 1

        # Deplacer le dessin des cases du motif
        y = 80
        for k in range(len(m)):
            x = 40 + 30 * (k + i)
            casesMotif[k].deplacer(x, y)

        # Deplacer le dessin des cases des valeurs de j
        x, y = 10 + 30 * i, 120
        caseJ.deplacer(x, y)
        for k in range(len(m)):
            x = 40 + 30 * (k + i)
            casesIndexJ[k].deplacer(x, y)

        # On met toutes les cases du motif mises en rouge car d'indice > à j en mode normal
        for case in l_cases_temp_droite:
            case.set_etat_contour(NORMALB)
            case.set_etat_texte(NORMALB)

        # On supprime de la liste des cases temporaires celles contenues dans la liste des cases des motifs trouvés
        for case in l_cases_temp:
            if case in l_cases_trouvees:
                l_cases_temp.remove(case)

        # On supprime aussi de l_cases_temp les cases de t qui correspondaient à une case à droite dans m
        for case in l_cases_temp:
            if case in l_cases_temp_t_droite:
                l_cases_temp.remove(case)

        # On met en mode NORMALB les cases de l_cases_temp_t_droite
        for case in l_cases_temp_t_droite:
            case.set_etat_contour(NORMALB)
            case.set_etat_texte(NORMALB)

        # On met en mode BON les cases étudiées  de l_cases_temp et en mode NORMALB celles en mode BON
        for case in l_cases_temp:
            if case.get_etat_contour() == ETUDIE:
                case.set_etat_contour(BON)
            elif case.get_etat_contour() == BON:
                case.set_etat_contour(NORMALB)
            if case.get_etat_texte() == ETUDIE:
                case.set_etat_texte(NORMALB)

        # On met toutes les cases de t des motifs trouvés en vert
        for case in l_cases_trouvees:
            case.set_etat_contour(BON)
            case.set_etat_texte(BON)

        # On met en mode normal toutes les cases d'indice
        for k in range(len(t)):
            casesIndexI[k].set_etat_contour(NORMALW)
        for k in range(len(m)):
            casesIndexJ[k].set_etat_contour(NORMALW)
        # On met en rouge la case de l'index i étudié
        casesIndexI[i].set_etat_contour(ETUDIE)
        # On met en rouge le contour de la case j = len(m) - 1
        casesIndexJ[len(m) - 1].set_etat_contour(ETUDIE)


NORMALB = 0
NORMALW = -2
BON = 1
ETUDIE = -1
dict_etat = {NORMALW: 'white', NORMALB: 'black', BON: 'green', ETUDIE: 'red'}


class Case():
    def __init__(self, can, x, y, cote, car, fonte, fg, bg, coulExt='black'):
        self.can = can
        self.IDRect = can.create_rectangle(
            x, y, x + cote, y + cote, fill=bg, outline=coulExt)
        self.etat_contour = coulExt
        self.etat_texte = fg
        self.etat_fond = bg
        self.car = car
        self.cote = cote
        self.fonte = fonte
        self.IDCar = can.create_text(
            x + cote / 2, y + cote / 2, text=car, font=fonte, fill=fg)

    def get_etat_contour(self):
        return self.etat_contour

    def get_etat_texte(self):
        return self.etat_texte

    def get_etat_fond(self):
        return self.etat_fond

    def set_etat_contour(self, e):
        self.etat_contour = e
        self.can.itemconfigure(self.IDRect, outline=dict_etat[e])

    def set_etat_texte(self, e):
        self.etat_texte = e
        self.can.itemconfigure(self.IDCar, fill=dict_etat[e])

    def set_etat_fond(self, e):
        self.fond = e
        self.can.itemconfigure(self.IDRect, fill=dict_etat[e])

    def deplacer(self, x, y):
        self.can.coords(self.IDRect, x, y, x + self.cote, y + self.cote)
        self.can.coords(self.IDCar, x + self.cote / 2, y + self.cote / 2)


A = input('Entrez un alphabet sous la forme d\'une chaîne de caractères: ')

# Demande du texte dont on cherche le motif
Alphabet = False
while not Alphabet:
    Alphabet = True
    t = input('Texte dans lequel on recherche un motif (31 caractères max): ')
    for c in t:
        if c not in A:
            Alphabet = False

# On limite à 31 caractères pour ne pas sortir de la feuille
if len(t) > 31:
    t = t[:31]

# Demande du motif
Alphabet = False
while not Alphabet:
    Alphabet = True
    m = input('Motif: ')
    for c in m:
        if c not in A:
            Alphabet = False
    if len(m) > len(t):
        Alphabet = False

# bougerMotif vaut True si il faut modifier le motif: i a été modifié
bougerMotif = False

# Remplissage du tableau de la dernière occurence des caractères de A dans m, ou -1 si le caractère n'appartient pas à m
R = calculR(m, A)

# Liste devant contenir les indexes dans t des motifs m trouvés
l_index_motifs = []
# Liste des cases remettre en mode BON (vert) au déplacement suivant du motif
l_cases_temp = []
# Liste des cases à remettre en mode normal et ayant matché (i >=0 et t[i+j] = m[j])
l_cases_temp_match = []
# Liste des cases du motif à droite (index k > j) et identiques au caractère t[i+j]
l_cases_temp_droite = []
# Liste des cases du texte qui correspondent à une case du motif à droite
l_cases_temp_t_droite = []
# Liste des cases d'un motif trouvé
l_cases_trouvees = []
# Index du début de la position du motif m et de la position relative dans le motif

i = 0
j = len(m) - 1

fen = Tk()
fen.title('Algorithme de Boyer-Moore')
fen.geometry('980x300+100+100')

# Création et placement du canvas
zoneDessin = Canvas(fen, height=200, width=980)
zoneDessin.grid(row=1, column=1, columnspan=len(t))
helv18 = tkFont.Font(family='Helvetica', size=18, weight='normal')
helv9 = tkFont.Font(family='Helvetica', size=9, weight='normal')

# Dessin des cases des valeurs de i
x, y, cote = 10, 10, 25
caseI = Case(zoneDessin, x, y, cote, 'i =', helv9, 'blue', 'white', 'white')
casesIndexI = []
for k in range(len(t)):
    x = 40 + 30 * k
    y = 10
    casesIndexI.append(
        Case(zoneDessin, x, y, cote, str(k), helv9, 'blue', 'white', 'white'))
# On met en rouge le contour de la case i = 0
casesIndexI[0].set_etat_contour(ETUDIE)

# Dessin des caractères de la chaîne t
casesTexte = []
for k in range(len(t)):
    x = 40 + 30 * k
    y = 40
    casesTexte.append(
        Case(zoneDessin, x, y, cote, t[k], helv18, 'black', 'yellow'))

# Dessin initial des caractères du motif
casesMotif = []
y = 80
for k in range(len(m)):
    x = 40 + 30 * k
    casesMotif.append(
        Case(zoneDessin, x, y, cote, m[k], helv18, 'black', 'yellow'))

# Dessin des cases des valeurs de j
x, y = 10, 120
caseJ = Case(zoneDessin, x, y, cote, 'j =', helv9, 'purple', 'white', 'white')
casesIndexJ = []
for k in range(len(m)):
    x = 40 + 30 * k
    casesIndexJ.append(
        Case(zoneDessin, x, y, cote, str(k), helv9, 'purple', 'white',
             'white'))
# On met en rouge le contour de la case j = len(m) - 1
casesIndexJ[len(m) - 1].set_etat_contour(ETUDIE)

#Création et placement du bouton permettant de déplacer le motif
boutonSuivant = Button(fen, text='Suivant', command=suivant)
boutonSuivant.grid(row=5, column=1, columnspan=len(t))

fen.mainloop()
?