Grundlegende Algorithmen: Lösungshinweise

Kapitel 6

6.1

Initialisiere eine neue Variable found=0; ersetze return i; durch found++; break; und ersetze return -1; durch return found;

6.2

border[]=(0,0,1,0,1,0,1,2,3,4)

6.3

S[]=(12,12,12,12,12,12,12,7,12,12,3,1)

6.4

Der Einfachheit halber nehmen wir an, dass n gerade und m ungerade ist: Wähle t=(ab)^n/2; s=a(ab)^m/2;

6.5

Der Suffix-Trie besitzt Θ(n²) Knoten.

6.6

Fleißaufgabe.

6.7

Konstruiere den Suffix-Baum für die konkatenierte Zeichenreihe und entferne Teilbäume die Dollarzeichen enthalten. Alternativ konstruiere einen Suffix-Baum für t₁. Konstruiere dann den Suffix-Baum für t_i innerhalb des bereits konstruierten Suffix-Baumes.

6.8

Komnstruiere einen verallgemeinerten Suffix-Tree T für x,y∈&Sigma^*. Markiere die Blätter mit x oder y, je nach dem, ob der zugehörige Suffix aus x oder y stammt. Der tiefste Knoten (gemäß der String-Tiefe) in T, der in seinem Teilbaum sowohl ein mit x als auch mit y markiertes Blatt besitzt, korrespondiert zum längsten gemeinsamen Teilwort.

6.9

Suche nach v in ww.

6.10

Suche nach dem zweiten Vorkommen von v in vv.

6.11

---

6.12

---