im Rahmen von Übung 3 müssen wir ja auch eine Lookup-Table für das vorgegebene Beispiel anfertigen. Ich habe mir zuächst - wie in den 2013er-Videos - einen Automaten gezeichnet und davon die Lookup-Table abgeleitet. Interessehalber habe ich dann versucht den Algorithmus zu verstehen, der im Algo-Wiki für die Erstellung der Lookup-Table verantwortlich ist (Induction basis -> Implementation -> Steps 3 - 4). Hierzu habe ich 2 Fragen:
1) In der Lookup-Table, die ich von meinem Automaten abgeleitet habe, hat [3,m] den Wert 1, was meiner Meinung nach richtig sein müsste. Wenn ich allerdings mithilfe der o.g. Schritte 3 - 4 der Induktionsbasis diesen Wert der Tabelle berechne, erhalte ich 0 als Ergebnis. Was ist nun richtig? 2) Schritt 4.2 aus dem Wiki lautet wir folgt: "While k > 0 and (T[1], ..., T[k]) != (T[j-k+2], ..., T[j], c), decrease k by 1." Im Folgenden versuche ich die besagte Position [3,m] der Lookup-Table zu berechnen.Code: Alles auswählen
j = 3 and c = "m"
4.1. Set k := min(m, j+ 1) = min(4, 4) = 4
4.2.1. k=4, (T[1], ..., T[4]) != (T[3-4+2], ..., T[3], "m"), da "meme" != "memm"
4.2.2. k=3, (T[1], ..., T[3]) != (T[3-3+2], ..., T[3], "m"), da "mem" != "emm"
4.2.3. k=2, (T[1], ..., T[2]) != (T[3-2+2], ..., T[3], "m"), da "me" != "mm"
4.3.4. k=1, (T[1], ..., T[1]) ?? (T[3-1+2], ..., T[3], "m"), ...Über eine Hilfestellung würde ich mich sehr freuen.
LG Lucas
