LCP-Array

Das LCP-Array ist eine Datenstruktur aus der Informatik, welche meist in Kombination mit dem Suffixarray verwendet wird. Die Bezeichnung „LCP“ ist eine Abkürzung für „longest common prefix“ (dt. längstes gemeinsames Präfix). Das Array selbst enthält die Länge des längsten gemeinsamen Präfixes von je zwei lexikographisch aufeinanderfolgenden Suffixen. Für das LCP-Array gibt es zahlreiche Anwendungen aus dem Bereich der Textsuche und -indizierung, wie beispielsweise die Konstruktion des Suffixbaums oder eine effiziente Suche aller Vorkommen eines Suchmusters in einem Text. Der benötigte Speicherplatz des LCP-Arrays ist linear im Vergleich zur Textgröße und es gibt Algorithmen, die das LCP-Array in linearer Zeit mit Hilfe des Suffixarrays konstruieren. Es wurde erstmals in einer Veröffentlichung von Manber und Myers (1993) benutzt, in der es als Hgt-Array bezeichnet wurde.