Abstrakt. Longest Common Extension (LCE) frågor är en grundläggande sub-rutin i många strängbehandlingsalgoritmer, inklusive (men inte begränsat till) suffix-sortering, strängmatchning, och identifiering av palindrom faktorer och upprepningar. En LCE-fråga tar som inmatning två positioner i, j i en text T  på n och returnerar längden l av det längsta gemensamma prefixet mellan T i-th och j-th suffixes. Det är tydligt att vi kan lagra T i n-log 2 och besvara LCE-frågor i O(l) tid genom att direkt jämföra de två suffix. Denna lösning har också fördelen av att stödja optimal tid textextraktion. I detta dokument, vi bevisa följande (något överraskande) resultat: i RAM-modellen, n-log 2  och bitar av utrymme är tillräckliga för att stödja deterministiska O(log 2 l)-tid LCE-frågor och optimal tid textextrahering. LCE frågetider kan förbättras till O(log l) genom att lägga till endast O(log n) ord till rymdanvändning. Med andra ord kan vi ersätta (den allmänna) texten med en datastruktur av samma storlek som stöder exponentiellt snabbare LCE-frågor utan att straffa textextraheringstider. Viktigt är att vår struktur kan byggas i O(n log n) förväntad tid och linjärt utrymme, och är därför också praktiskt. Genom att tillämpa våra tekniker på suffix sorteringsproblem, får vi (i) en ny in-place suffix array konstruktionsalgoritm och (ii) den första effektiva på plats lösning för sparse suffix sortering problem.
Nyligen har fingeravtryck tillämpats på den längsta gemensamma utbyggnaden (LCE) problem REF, vilket gör det möjligt att lösa LCE-frågor i logaritmisk tid i huvudsak samma utrymme som indatatexten (ersättning av texten med en datastruktur av samma storlek).
In-Place Longest Common Extensions
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}