[PYTHON] String-Suchalgorithmus

Ich möchte ein Zeichenkettenmuster aus einer Zeichenkette finden.

Es gibt Zeiten, in denen Sie herausfinden möchten, ob ein Zeichenfolgenmuster aus einer Zeichenfolge besteht. In einem solchen Fall haben wir drei perfekte Algorithmen implementiert.

Ich werde einen Kommentar hinzufügen, wenn ich Zeit habe.

Zunächst ein Programm, das eine zufällige Zeichenfolge generiert

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"]))

Jetzt werde ich von hier aus drei Algorithmen zur Suche nach Zeichenketten einführen.

Brute Force (Gori Push)

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"))

#Unten, mit regulären Ausdrücken, brutal_4. Überprüfen Sie, ob Argo die richtige Ausgabe erzeugt
import re

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

KMP-Methode

from make_random_str import random_str

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

def kmp(string, pattern):
    #Erstellen Sie zunächst eine Tabelle aus dem Muster, wie viele verschoben werden sollen
    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"))

#Unten, mit regulären Ausdrücken, brutal_4. Überprüfen Sie, ob Argo die richtige Ausgabe erzeugt
import re

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

BM-Methode

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)

    #Erstellen Sie zuerst eine Tabelle
    #Da ASCII verwendet wird, wird eine Tabelle mit einer Länge von 256 erstellt.
    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
        #Vergessen Sie nicht, max
        i = i + max(table[ord(string[i])], lp-j)
    if not ans:
        return -1
    return ans

print(bm(string, "ABCDE"))

#Unten, mit regulären Ausdrücken, brutal_4. Überprüfen Sie, ob Argo die richtige Ausgabe erzeugt
import re

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