Textsuche < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:54 Di 19.09.2006 | | Autor: | G3kkoo |
| Aufgabe | Gegeben sei folgende Zeichenkette: bcbabbabbcbcaabbabbacaaabba sowie der Suchbegriff abba
Bestimmen Sie die Anzahl der Suchschritte für die Verfahren:
Naiv, Knuth-Morris-Pratt & Boyer-Moore. |
Hallöchen,
also die Suche mit Naiv habe ich auf die Reihe bekommen und bin insgesamt auf 43 Suchschritte gekommen.
Mein Problem ist, dass ich selbst mit Literatur die anderen zwei Verfahren nicht auf die Reihe bekomme bzw sie verstehe..
Hat da jemand einen Rat, Ahnung, Idee??
Vielen Dank im Voraus!
Jenny
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 21:51 Di 19.09.2006 | | Autor: | G3kkoo |
Zum Knuth-Morris-Pratt habe ich folgendes herausgefunden (mit Hilfe von Wikipedia):
Anzahl der Schritte: 21, wobei mein Rand stets 1 Feld breit war..
Ob ich es richtig umgesetzt habe?
|
|
|
| |
|
h t t p : / / w w w .r z.r w t h- aa ch en .de /mata/downloads/algo_dat/folien2006/AlgoDat2006_Teil16.pdf
In diesem PDF File wird es recht gut erklärt.
Beim Naiven Verfahren wird jedes Zeichen einzeln verglichen.
Bei Knuth-Morris hingegen gibt es Sprünge.
|
|
|
|
