String Matching Algorithmus Design

Question

Gegeben ein Text t [1 ... n] und k Muster p1, p2, ... pk jeweils der Länge m, n = 2m, aus dem Alphabet [0, Sigma-1]. Entwerfen Sie einen effizienten Algorithmus, um alle Orte in t zu finden, an denen eines der Muster pjs übereinstimmt.

Also habe ich eine Zeichenfolge t = "1 2 3 4 5 2 2 9" und das Muster p = "4 5 2 2". Ich weiß, dass es m + 1 Orte geben wird, an denen ich ein Muster finden kann (entweder von "1 2 3 4", "2 3 4 5", etc ...).

Dann haben wir k Zeichen in dem Muster, so dass das bigO out zu O (k (m + 1)) kommt.

Mein Algorithmus wäre, die Zeichenfolge zu durchsuchen, die jedes Zeichen mit den Zeichen in dem Muster überprüft. Das führt mich zu Wiederholungen für m + 1 Standorte.

Hoffentlich erkläre ich es richtig. Ich möchte nur wissen, ob ich es richtig mache und ob es irgendwelche Fehler in meiner Logik gibt. Vielen Dank!

Answer 1

Mein Algorithmus wäre, die Zeichenfolge zu durchsuchen, die jedes Zeichen mit den Zeichen im Muster überprüft. Das wird mich k Iterationen für m + 1 Standorte führen.

Das bedeutet für jedes Muster, können Sie es tun O (m + 1), oder?

Obwohl es Algorithmen gibt, die diese Leistung erreichen können, ist Ihre Brute Force nicht. Sie haben m + 1 Standorte und für jeden Standort müssen Sie m Zeichen überprüfen, so dass die Gesamtkomplexität für jedes Muster O (m (m + 1)) ist.