python élégant

Tout d'abord, jetons un coup d'œil à la simple correspondance des chaînes

Cela peut être imaginé comme fixant la chaîne de texte s et alignant la chaîne de motif p en commençant par le côté le plus à gauche de s. Si les parties alignées sont exactement les mêmes, si la correspondance est réussie, si elle échoue, toute la chaîne de motif p sera décalée d'une position vers la droite, et la partie d'alignement continuera à être vérifiée, et ainsi de suite

#Naive match

def naive_match(s , p):
m = len(s); n = len(p)
pour i dans la plage (m-n 1):#Start pointer i
if s[i:i n] == p ; 🎜>En fait, il s'agit de prétraiter la chaîne de modèle p pour obtenir une table de correspondance partielle de suffixes et de suffixes, afin que nous peut utiliser des informations connues pour calculer combien de bits peuvent être décalés vers la droite. C'est-à-dire kmp = correspondance simple pour décaler plusieurs bits.
Plus Veuillez consulter l'article de Ruan Yifeng pour plus de détails, que je n'aborderai pas ici <.>L'implémentation du code python est donnée ci-dessous

#KMP

def kmp_match(s, p) :
m = len(s); n = len(p)

cur = 0#Start pointer cur

table = partial_table(p )
while cur<=m-n:

pour i in range(n):

if s[i cur]!=p[i]:
cur = max(i - table[i- 1], 1)# Avec la table de correspondance partielle, on ne fait pas il suffit de déplacer d'un bit vers la droite, nous pouvons déplacer plusieurs bits à la fois
                pause
            else:
                                      ' s ' ' à ' s ' t ‐ ‐ ‐ ‐                                                                                                    . 🎜>
#Partiel table correspondante
def partial_table(p):
'''partial_table("ABCDABD") -> [0, 0, 0, 0, 1, 2, 0]'' '
préfixe = défini ()
postfix = set()
ret = [0]
pour i in range(1,len(p)):
prefix.add(p[ :i])
postfix = {p[j:i 1] for j in range(1,i 1)}
ret.append(len((prefix&postfix or {''}).pop()) )
return ret

print naive_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD")
print partial_table("ABCDABD")
print kmp_match("BBC ABCDAB ABCDABCDABDE", "ABCDABD" )



Ce qui précède est le contenu d'élégant python. Pour plus de contenu connexe, veuillez faire attention au site Web PHP chinois (www.php.cn) !