0 Daumen
21 Aufrufe

Mithilfe der LCP-Werte ist es möglich, die Binärsuche in einem Suffixarray zu beschleunigen. Nehmen Sie an, dass Sie die LCP-Werte von benachbarten Einträgen in einem Suffixarray gegeben haben. Das heißt, Sie haben n-1 viele LCP-Werte für einen String der Länge n.

Frage:

a) Um die Binärsuche durchführen zu können, brauchen Sie noch weitere LCP-Werte. Welche LCP-Werte benötigen Sie zusätzlich?
b) Wie viele LCP-Werte brauchen Sie dann genau (keine O -Notation!) und wie können Sie die weiteren LCP-Werte aus a) effizient berechnen?

von

1 Antwort

0 Daumen

blob.png

Ich bin nicht sicher, aber so würde ich das machen

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community