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?
