Verstehen des Algorithmus für den Mustervergleich mithilfe eines LCP-Arrays
Vorwort: Meine Frage ist hauptsächlich eine algorithmische Frage. Selbst wenn Sie mit Suffix- und LCP-Arrays nicht vertraut sind, können Sie mir wahrscheinlich helfen.
ImDie paper Es wird beschrieben, wie Suffix- und LCP-Arrays für den String-Pattern-Matching effizient verwendet werden können.
Ich habe verstanden, dass SA und LCP funktionieren und wie die Laufzeit des Algorithmus von @ verbessert werden kanO(P*log(N))
(woP
ist die Länge des Musters undN
ist die Länge der Zeichenkette) bisO(P+log(N))
(Danke an Chris Eelmaa's AntwortHie und Jogojapans antwortenHie).
Ich habe versucht, den in Abbildung 4 gezeigten Algorithmus zu durchlaufen, der die Verwendung von @ erklärLLcp
undRLcp
. Aber ich habe Probleme zu verstehen, wie es funktioniert.
Der Algorithmus (entnommen ausdie Quell):
Erläuterung der verwendeten Variablennamen:
lcp(v,w) : Length of the longest common prefix of v and w
W = w0..wP-1 : pattern of length P
A = a0..aN-1 : the text (length N)
Pos[0..N-1] : suffix array
L_W : index (in A) of first occurrence of the matched pattern
M : middle index of current substring
L : lower bound
R : upper bound
Lcp : array of size N-2 such that Lcp[M] = lcp(A_Pos[L_M], A_pos[M]) where L_M is the lower bound of the unique interval with M in the middle
Rcp : array of size N-2 such that Rcp[M] = lcp(A_Pos[R_M], A_pos[M]) where R_M is the upper bound of the unique interval with M in the middle
Nun möchte ich den Algorithmus anhand des folgenden Beispiels ausprobieren (teilweise aus @ entnommeHie):
SA | LCP | Suffix entry
-----------------------
5 | N/A | a
3 | 1 | ana
1 | 3 | anana
0 | 0 | banana
4 | 0 | na
2 | 2 | nana
A = "banana" ; N = 6
W = "ban" ; P = 3
Ich möchte versuchen, eine Zeichenfolge zu finden, sagen Sieban
und würde erwarten, dass der Algorithmus 0 als @ zurückgiL_W
.
Hier ist, wie ich den Algorithmus schrittweise durchlaufen würde:
l = lcp("a", "ban") = 0
r = lcp("nana", "ban") = 0
if 0 = 3 or 'b' =< 'a' then // which is NOT the case for both conditions
L_W = 0
else if 0 < 3 or 'b' =< 'n' then // which is the case for both conditions
L_W = 6 // which means 'not found'
...
...
Ich habe das Gefühl, dass mir etwas fehlt, aber ich kann nicht herausfinden, was. Außerdem frage ich mich, wie das vorberechnete LCP-Array verwendet werden kann, anstatt @ aufzurufelcp(v,w)
.