SimpleStringMatching & SimpleStringMatchingBOFA

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 201
Registriert: 12. Apr 2015 11:35

SimpleStringMatching & SimpleStringMatchingBOFA

Beitrag von sqrt(2) » 21. Apr 2016 14:11

Hallo,

eine Sache verstehe ich nicht ganz. Wie würde die Implementation der beiden Algorithmen aussehen um einen gültigen Kandidaten in die Ergebnismenge R aufzunehmen?

SSM:
Wie wird der gültige und vollständige Kandidat in die Ergebnismenge R aufgenommen? Speichert man sich die Länge des Strings T ab und prüft ob:

i. in Nabla
beim Tupel aus (Startindex, Anzahl gültiger Kandidaten [von 0 angefangen zu zählen]), die "Anzahl gültiger Kandidatenlänge" + 1 = |T| entspricht und speichert sich dann den "Startindex" in der Ergebnismenge R?

ii. auf den Folien
hier ist mir nicht klar anhand von welcher Information man sehen sollte (bzw. die Implementation erfolgen sollte), dass man nun den Startindex eines vollständigen und gültigen Kandidaten in die Ergebnisliste R aufnehmen kann, da nirgends der Startindex gespeichert wird (wie in Nabla bspw.)

BOFA:
Hier könnte ich mir die Implementation so vorstellen, sobald man an den Zustand |T| gelangt (also die Zahl des Zustands entspricht der Länge des Strings T), subtrahiert man p von i und erhält den Startindex s. Wobei p, i und s wie folgt in Beziehung zueinander stehen:

Code: Alles auswählen

q = delta(p, S[i]) 
und

Code: Alles auswählen

s = i - p

Gruß

Zurück zu „AuD: Vorlesung“