Aufgabe 40: Teilwortsuche mit Hilfe der Verschiebefunktion

Lösungsvorschläge zum 7. Aufgabenblatt zur Vorlesung
Algorithmen und Datenstrukturen III
WiSe 2015/2016
Günter Rote
Aufgabe 40 Teilwortsuche
6 Punkte
Gegeben ist m = |x|, n = |y| mit n > m und die Verschiebefunktion f von c := xy.
Ein Rand eines Wortes w sei ein Präfix von w, das auch ein Suffix von w ist. Ein
Rand von w sei ein echter Rand, wenn er ungleich w ist.
Zunächst stellen wir fest, dass, da x ein Präfix von c ist, x genau dann in c an den
Stellen j +1 bis j +m vorkommt, wenn c1 ...cj+m einen Rand der Länge |x| = m hat.
Dieser Rand muss echt sein, wenn j > 0, da dann |c1 ...cj+m | > m. x ist Teilwort
von y gdw. x in c irgendwo ab der Stelle m + 1 vorkommt. Zusammen gilt also:
x Teilwort von y ⇐⇒
⇐⇒
⇐⇒
⇐⇒
x kommt in c irgendwo ab der Stelle m+1 vor
∃j ≥ m + 1 : x = cj ...cj+m−1
∃j ≥ m + 1 : c1 ...cm = cj ...cj+m−1
∃j ≥ m + 1 : c1 ...cj+m−1 hat Rand der Länge m
i=j+m−1
⇐⇒ ∃i ≥ 2m : c1 ...ci hat Rand der Länge m
Die Verschiebefunktion liefert leider nur den jeweils größten echten Rand jedes
Präfixes, man kann aber nicht direkt ablesen, ob ein Rand der Länge m existiert.
Rekursiv kann dies aber mithilfe der Verschiebefunktion bestimmt werden. Dafür
wird folgende Hilfsfunktion definiert, die bestimmt, ob das Präfix von c der Länge
i einen echten Rand der Länge m hat:
Rand : 1, ..., m + n → T rue, F alse



T rue
falls f [i] = m
Rand(i) = F alse
falls f [i] < m



Rand(f [i]) falls f [i] > m
Die Korrektheit dieser Funktion soll nun durch Induktion nach i bewiesen werden.
Induktionsanker (i<=m): Da offensichtlich f [i] < i, kann nur der zweite Fall auftreten. Das ist richtig, da ein Wort der Länge ≤ m kein echten Rand der Länge m
haben kann.
Induktionsvorraussetzung: Rand(j) ist korrekt für j = 1, ..., (i − 1).
Induktionsschritt (→ i):
f [i] = m besagt, dass der größte Rand des betrachteten Präfix c1 ...ci die Länge m
hat, also ein Rand der Länge m offensichtlich existiert.
f [i] < m besagt, dass der größte Rand von c1 ...ci kleiner als m ist. Daher kann in
diesem Fall ein Rand der Länge m nicht existieren.
In den ersten beiden Fällen ist die Funktion also korrekt. Da die Induktionsvorraussetzung besagt, dass Rand für f [i] korrekt ist, weil f [i] < i, bleibt zu beweisen,
dass, falls f [i] > m:
c1 ...ci hat echten Rand der Länge m ⇐⇒ c1 ...cf [i] hat echten Rand der Länge m
Da i > f [i] > m kann genau so gut gezeigt werden:
c1 ...ci hat Rand der Länge m ⇐⇒ c1 ...cf [i] hat Rand der Länge m
Sei r = f [i]. Wir wissen, dass c1 ...ci einen Rand der Länge r hat, also
c1 ...cr = ci−r+1 ...ci
⇐⇒ ∀j ≤ r : cj ...cr = ci−r+j ...ci
=⇒ c(r−m+1) ...cr = ci−r+(r−m+1) ...ci
⇐⇒ cr−m+1 ...cr = ci−m+1 ...ci
(1)
Es gilt:
c1 ...cr hat Rand der Länge m
⇐⇒ c1 ...cm = cr−m+1 ...cr
(1)
⇐⇒ c1 ...cm = ci−m+1 ...ci
⇐⇒ c1 ...ci hat Rand der Länge m
Folgendes Bild veranschaulicht den letzten Schritt im Fall, dass c1 ...cr einen Rand
der Länge i hat (unten mit b bezeichnet) und unter Nichtbeachtung möglicher Überlappungen:
a
a
}|
z
{
z
}
|
}|
{
c ...c c
...cr−m cr−m+1 ...cr cr+1 ...ci−r ci−r+1 ...ci−r+m . ci−r+m+1 ...ci−m ci−m+1 ...ci
| 1 {z m} m+1
b
|
{z
b
{z
b
}
|
{z
b
}
Wenn Rand(i) naiv ausgeführt wird, ist die Laufzeit im schlimmsten Fall (f [i] =
P|c|
[0, 1, 2, ...] und n ≥ c · m, c > 1) gleich i=2m i ∈ Θ(|c|2 ). Wenn allerdings die
von Rand(i) errechneten boolschen Werte zwischengespeichert werden, benötigt
man |c| − 2m + 1 Aufrufe, kommt also auf die Laufzeit Θ(|c|) = Θ(m + n). Da
die Verschiebefunktion von |c| ebenfalls in Θ(m + n) Zeit bestimmt werden kann,
ergibt sich so ein Algorithmus der (asymptotisch) gleichen Laufzeit wie der von
Knuth-Morris-Pratt.

Download Report