Seite 1 von 1

Wiki: Simple String Matching

Verfasst: 23. Apr 2016 17:59
von sqrt(2)
Quelle: https://wiki.algo.informatik.tu-darmsta ... ction_step

Hallo,

ich verstehe beim Induktionsschritt den Punkt 2.2 der Abstrakten Sicht nicht ganz. Meine Fragen:

a. Warum hat man hier die Bedingung eingeführt das I nicht die leere Menge sein darf?
b. "and i-m+1 is the head element of I" -> Ist meine Auffassung richtig, dass man hier prüft ob vom aktuellen Laufindex i geschaut wird, ob die Gleichung [i-m+1] mit dem ersten Element der Sequenz I überein stimmt? Wenn ja hat man aufgrund von 1. einen vollständigen und gültigen Kandidaten. Ungültige Kandidaten wurden ja dank 1. Satz 2 entfernt.
c. Warum ist I nur eine ordered Sequence und keine sorted Sequence? (Weil wir keinen Vergleich c direkt auf I anwenden, sondern nur Elemente in I reinpacken die "zufällig" aufgrund der Nummerierung der einzelnen Positionen i sortiert ist?)

Re: Wiki: Simple String Matching

Verfasst: 23. Apr 2016 18:10
von sqrt(2)
b hat sich durch Correctness 1. geklärt.

Re: Wiki: Simple String Matching

Verfasst: 24. Apr 2016 09:22
von Prof. Karsten Weihe
sqrt(2) hat geschrieben: ich verstehe beim Induktionsschritt den Punkt 2.2 der Abstrakten Sicht nicht ganz. Meine Fragen:
a. Warum hat man hier die Bedingung eingeführt das I nicht die leere Menge sein darf?
Weil danach in 2.2 sofort auf das "head element" von I zugegriffen wird, dass ja im Falle einer leeren Menge I nicht existiert.

Da Sie in einem Follow-Up geschrieben haben, dasss Ihre Frage b sich geklärt hat, gehe ich darauf also nicht ein.

KW

Re: Wiki: Simple String Matching

Verfasst: 24. Apr 2016 14:52
von sqrt(2)
Okay, danke :)