Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Z-Algorithmus und Knuth-Morris-Pratt
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Informatik-Forum -> Z-Algorithmus und Knuth-Morris-Pratt
 
Autor Nachricht
Sun_Boy
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 23.11.2005
Beiträge: 33

BeitragVerfasst am: 24 Jun 2007 - 09:52:28    Titel: Z-Algorithmus und Knuth-Morris-Pratt

Hallo zusammen,

ich bereite mich gerade auf die Prüfung Algorithmen und Datenstruktur vor (18.07) und habe da Probleme mit 2 Aufgaben. Da geht es um den z-Algorithmus und den KMP.

1.) Gegeben sei das Textmuster P= abcxababcxacbaxabxabcxa. Berechnen Sie
a.) die Menge der Z-Boxen für die Positionen 1 bis 22
b.) mit dem Z-Algorithmus, die Menge der Vorkommen in dem Text:
T= abcxabcabcxababcxacbaxabxabcxabcxababcxacbaxabxabcxababcxacbaxabxabcxa

Also zu a.) hätte ich sowas gedacht-> Z1(P)=0; Z2(P)=0; Z3(P)=0; Z3(P)=0; Z4(P)=2 etc... bis Z22(P)= 1

Bin mir allerdings nicht sicher, ob das wirklich die Z-Boxen sind bzw. ob das in der Aufgabe verlangt wurde Sad

Zu b.) habe ich keine Ahnung. Wie genau funktioniert der Algorithmus ?

Dann noch eine Aufgabe zum KMP
Gegeben sei der Text T=aababcbabcabcabbcabab und das Muster P=abcabbcab.
Wieviele Vergleiche brauchen Sie für die Lösung des exact-String-matching Problems mit dem Algorithmus von Knuth, Morris und Pratt ?

Wie genau funktioniert der Algorithmus ? Werde da aus dem Skript nicht wirklich schlau. Ist aber auch sehr unvollständig Sad(

Danke schonmal!

Viele Grüsse
Sunny
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Informatik-Forum -> Z-Algorithmus und Knuth-Morris-Pratt
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum