KMP-Ausfall-Funktion-Berechnung

Mein professor löste das kmp-Ausfall-Funktion wie folgt:

index  1 2 3 4 5 6 7 8 9
string a a b a a b a b b
ff     0 1 2 1 2 3 4 5 1

Aus anderen Texte, die ich online überprüft, fand ich heraus, dass es falsch sein könnte, ging ich zurück, um zu bestätigen, von ihm wieder und er sagte mir, er hat absolut Recht. Kann jemand pls erklären mir, warum er denkt, dass es richtig oder falsch, eine einfache Schritt für Schritt-Weise? Dank

Möglicherweise müssen Sie subtrahieren eines aus jedem Wert in die fail Tabelle. Es kommt auf den Algorithmus, die Sie verwenden.

InformationsquelleAutor Dennis | 2013-04-20

  1. 17

    So wie ich das verstehe ist der Algorithmus, der Fehler-Funktion für Ihr Beispiel sollte die folgende sein:

    1 2 3 4 5 6 7 8 9

    a a b a a b a b b

    0 1 0 1 2 3 4 0 0

    f - failure-Funktion (per definition ist dies die Länge des längsten Präfix der Zeichenfolge, die ein suffix auch)

    Hier, wie ich baute es Schritt für Schritt:

    f(a) = 0 (immer = 0 für einen Buchstaben)

    f(aa) = 1 (einen Buchstaben 'a' ist sowohl ein Präfix und suffix)

    f(aab) = 0 (es gibt keine gleichen Suffixe und Präfixe: a != b, aa != ab)

    f(aaba) = 1 ('a' ist der gleiche Anfang und das Ende, aber wenn Sie 2 Buchstaben, werden Sie nicht gleich sein: aa != ba)

    f(aabaa) = 2 ( können Sie 'aa', aber nicht mehr: aab != baa)

    f(aabaab) = 3 ( können Sie 'aab')

    f(aabaaba) = 4 ( können Sie 'aaba')

    f(aabaabab) = 0 ( 'a' != 'b', 'aa' != 'ab' und so weiter, kann es nicht = 5, also als 'aabaa' != 'aabab')

    f(aabaababb) = 0 ( die gleiche situation)

    InformationsquelleAutor user2513978

Schreibe einen Kommentar