[infostudents] Re: Aufgabe2 KMP

  • From: don.vito.c@xxxxxx
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Sun, 25 Jan 2009 11:35:38 +0100

Auf dieser Seite gibt es (ganz unten) eine funktionsfähige Java-Implementation. Um den Next-Array auszugeben sind nur geringe Änderungen erforderlich. Richtig ist aber auf jeden Fall [-1, 0, 0, 0, 1, 2, 3, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6]
http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm

Natascha Widder schrieb:


Hallo,

Hier Aufgabe2, hat das Ergebnis sonst noch jemand rausbekommen?
 

Aufgabe2

T=BARBARBARBARBARASRABARBARASRABARBARBAR

P= BARBARASRABARBAR


a)

Next-Array: [0,0,0,1,2,3,1,0,1,2,1,2,3,4,5,6]

next[16] = 6


b)

T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR


P ist Teil von T



T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR

Fehler an Stelle 7. Jedoch Wort Bar aus Text an Stelle 4-6 im Muster => verschieben



T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR


Weiter abgleichen:




T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR

Fehler an Stelle 10. Jedoch Wort Bar aus Text an Stelle 8-10 im Muster => verschieben


T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR

Wort gefunden. Gib Treffer aus und verschiebe um Präfix (6)





T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR

Fehler an Stelle 16. Verschieben bis zum nächsten B





T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR

Wort gefunden. Gib Treffer aus und verschiebe um Präfix (6)






T = BARBARBARBARBARASRABARBARASRABARBARBAR

P = BARBARASRABARBAR

fertig






NUR NOCH BIS 31.01.! WEB.DE FreeDSL - Telefonanschluss + DSL   
für nur 16,37 EURO/mtl.!* http://dsl.web.de/?ac=OM.AD.AD008K13805B7069a  
--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents

Other related posts:

  1. Home
  2. infostudents
  3. Archive
  4. 01-2009