LCPstructuren

LCPstructuren zijn datastructuren die informatie vastleggen over de langste gemeenschappelijke prefix (LCP) tussen suffixes van een tekenreeks. Ze staan meestal in dienst van tekstindexering en patroonmatching, omdat ze snelle LCP-queries mogelijk maken tussen paren suffixes of tussen suffixes en posities in de tekst.

Een gangbare opzet van een LCPstructuur bevat doorgaans een suffix-array (SA), een LCP-array en een mechanisme voor range minimum queries (RMQ) op de LCP-array. Met deze combinatie kan de lengte van de LCP tussen twee suffixes i en j in constante tijd worden berekend nadat de structuur is gepreprocessd. De preprocessing vereist doorgaans lineaire tijd en lineaire aaneengeschakelde ruimte.

Constructie en varianten: de LCP-array kan met het Kasai-algoritme in O(n) tijd worden berekend uit de string en de suffix-array. Voor snelle LCP-queries wordt op de LCP-array een RMQ-structuur gebouwd, bijvoorbeeld via een Cartesian-tree of segmentboom, waardoor LCP(i, j) in O(1) tijd beschikbaar is. Er bestaan ook dynamische varianten die updates toestaan (bijvoorbeeld bij bewerkingen in de tekst) en compressievarianten die minder geheugen vereisen door gebruik te maken van bitvectoren of wavelet-gegenereerde structuren. Sommige implementaties integreren LCPstructuren in bredere indexstructuren zoals suffix trees, suffix arrays of FM-indexen.

Toepassingen: LCPstructuren worden toegepast bij snel substring-zoek en patroonmatching, tekstindexering en repetitiviteitsanalyse, en in bio-informatica voor vergelijking van DNA- of eiwitreeksen, waar snelle LCP-berekeningen de uitvoeringssnelheid van alignering en zoekopdrachten verbeteren.

Zie ook: suffix-array, RMQ, Kasai-algoritme, Cartesian-tree.