Suffix träd och suffix arrays är de mest framträdande full-text index, och deras konstruktion algoritmer är väl studerade. I litteraturen kör den snabbaste algoritmen i O(n) tid, medan den kräver O(n log n)-bit arbetsutrymme, där n betecknar textens längd. Å andra sidan kräver den mest rymdeffektiva algoritmen O(n)-bit arbetsutrymme medan den körs i O(n log n) tid. Det var öppet om dessa index kan konstrueras i både o(n log n) tid och o(n log n)-bit arbetsyta. Detta papper bryter ovanstående tids- och rymdbarriär under enhetskostnadsordets RAM. Vi ger en algoritm för att bygga suffix array som tar O(n) tid och O(n)-bit arbetsutrymme, för texter med konstant storlek alfabet. Observera att både tid och rymdgränser är optimala. För att bygga suffixträdet, kräver vår algoritm O(n log n) tid och O(n)-bit arbetsyta för alla 0 < < 1. Bortsett från detta kan vår algoritm också användas för att bygga andra befintliga fulltextindex, såsom Compressed Suffix Tree, Compressed Suffix Arrays och FM-index. Vi studerar också det allmänna fallet där alfabetets storlek inte är konstant. Vår algoritm kan konstruera en suffix array och ett suffix träd med hjälp av optimal O(n log  och)-bitars arbetsyta medan du kör i O(n log  och O(n(log n + log)) tid, respektive. Dessa är de första algoritmer som uppnår o(n log n) tid med optimal arbetsyta. Dessutom, för det speciella fallet där log  på = O (log log n) 1- ), kan vi snabba upp vår suffix array byggalgoritm till den optimala O (n).
Suffix matriser kan konstrueras i O(N) tid med hjälp av O(N) arbetsutrymme REF ].
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
{'venue': 'SIAM J. Comput.', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}