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)

Recommended Posts

Algorithme de recherche de chaînes
Algorithme de recherche utilisant word2vec [python]
Algorithme en Python (dichotomie)
Algorithme en Python (recherche de priorité de largeur, bfs)
Algorithme en Python (recherche de priorité en profondeur, dfs)
[Algorithme de langage C] arbre de recherche binaire
Gymnastique algorithmique 12
Gymnastique algorithmique 10
Exercice d'algorithme 6
Format de chaîne
Gymnastique algorithmique 9
Gymnastique algorithmique 14
Gymnastique algorithmique 2
Gymnastique algorithmique 7
Gymnastique algorithmique 15
Algorithme Python
Rechercher le labyrinthe avec l'algorithme python A *
Format de chaîne 2
Gymnastique algorithmique 16
Résumé de la chaîne de caractères 1
Gymnastique algorithmique 8
chaîne brute
Exercices d'algorithme 13
Gymnastique algorithmique 17
Chaîne Python
Gymnastique algorithmique 18
Gymnastique algorithmique 11
Exercice d'algorithme 5
Gymnastique algorithmique 4
Qu'est-ce qu'un algorithme? Introduction à l'algorithme de recherche] ~ Python ~