[PYTHON] Algorithme de recherche de chaînes

Je veux trouver un modèle de chaîne de caractères à partir d'une chaîne de caractères.

Tout le monde, il y a des moments où vous voulez savoir si un modèle de chaîne existe à partir d'une chaîne. Dans un tel cas, nous avons implémenté trois algorithmes parfaits.

J'ajouterai un commentaire quand j'aurai du temps libre.

Tout d'abord, un programme qui génère une chaîne de caractères aléatoire

import random

def random_str(x, char_list):
    return "".join([random.choice(char_list) for _ in range(x)])

if __name__ == "__main__":
    print(random_str(10, ["a","b","c","d"]))

Maintenant, je vais présenter trois algorithmes de recherche de chaînes de caractères à partir d'ici.

Force brute (poussée de Gori)

from make_random_str import random_str

string = random_str(10000,["A","B","C","D","E"])

def brute_forth(string, pattern):
    i = 0
    j = 0
    lp = len(pattern)
    ls = len(string)
    ans = []
    while i <= ls-1:
        if string[i] == pattern[j]:
            if j == lp-1:
                ans.append(i-lp+1)
                i +=1
                j = 0
            else:
                i += 1
                j += 1
        else:
            i = i-j+1
            j = 0
    if not ans:
        ans = -1
    return ans

print(brute_forth(string,"ABCDE"))

#Ci-dessous, en utilisant des expressions régulières, brute_Vérifiez si Argo produit la sortie correcte
import re

L =[]
check = re.finditer(r"ABCDE", string)
for i in check:
    L.append(i.span()[0])
print(L)

Méthode KMP

from make_random_str import random_str

string = random_str(1000000, ["A","B","C","D","E"])

def kmp(string, pattern):
    #Tout d'abord, créez un tableau à partir du modèle du nombre à décaler
    table = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        if pattern[i] == pattern[j]:
            table[i] = j
            j += 1
        else:
            j = 0

    ans = []
    s = 0
    t = 0
    while s < len(string):
        if string[s] == pattern[t]:
            if t == len(pattern)-1:
                ans.append(s-t)
                s += 1
                t = 0
            else:
                s += 1
                t += 1
        elif t == 0:
            s += 1
        else:
            t = table[j]
    return ans


print(kmp(string, "ABCEABC"))

#Ci-dessous, en utilisant des expressions régulières, brute_Vérifiez si Argo produit la sortie correcte
import re

L =[]
check = re.finditer(r"ABCEABC", string)
for i in check:
    L.append(i.span()[0])
print(L)

Méthode BM

from make_random_str import random_str

string = random_str(10000,["A","B","C","D","E"])

def bm(string,pattern):

    lp = len(pattern)
    ls = len(string)

    #Créez d'abord une table
    #Puisque ascii est utilisé, une table d'une longueur de 256 est préparée.
    table = [lp for _ in range(256)]
    for i in range(lp):
        table[ord(pattern[i])] = lp-i-1

    ans = []
    i = lp - 1
    while i < ls:
        j = lp - 1
        while string[i] == pattern[j]:
            if j == 0:
                ans.append(i)
            i -=1
            j -=1
        #N'oubliez pas de prendre max
        i = i + max(table[ord(string[i])], lp-j)
    if not ans:
        return -1
    return ans

print(bm(string, "ABCDE"))

#Ci-dessous, en utilisant des expressions régulières, brute_Vérifiez si Argo produit la sortie correcte
import re

L =[]
check = re.finditer(r"ABCDE", string)
for i in check:
    L.append(i.span()[0])
print(L)