Abstrakt. Ett fulltextindex är en datastruktur byggd över en textsträng T [1, n]. Den mest grundläggande funktionaliteten är a) räkna hur många gånger en mönstersträng P [1, m] visas i T och b) lokalisera alla dessa occ positioner. Det finns flera index som löser a) i O(m) tid och b) i O(occ) tid. I detta dokument föreslår vi två nya frågor, c) räkna hur många gånger P [1, m] förekommer i T [l, r] och d) lokalisera alla dessa occ l,r positioner. Dessa kan lösas med hjälp av a) och b) men detta kräver O(occ) tid. Vi presenterar två lösningar på (c) och (d) i detta dokument. Det första är ett index som kräver O(n log n) bitar av utrymme och svar (c) i O(m + log n) tid och d) i O(log n) tid per förekomst (dvs. O(occ l,r log n) tid totalt). En variant av den första lösningen svarar (c) i O(m + log log n) tid och (d) i konstant tid per händelse, men kräver O(n log 1 + på n) bitar av utrymme för varje konstant  till > 0. Den andra lösningen kräver O (nm log σ) bitar av utrymme, lösa (c) i O (m enlog σ/ log log n på) tid och (d) i O (m enlog σ/ log log n på) tid per händelse, där σ är alfabetets storlek. Denna andra struktur tar mindre plats när texten är komprimerad. Våra lösningar kan ses som en generalisering av rankning och välja ordböcker, som gör det möjligt att beräkna hur många gånger en given tecken c visas i en prefix T [1, i] och även lokalisera den i-th förekomsten av c i T. Vår lösning till (c) utökar tecken rank frågor till substring rank frågor, och vår lösning till (d) utökar tecken väljer att substring välj frågor. Som en biprodukt, visar vi hur rank frågor kan användas för att genomföra fraktionerad kaskadering i lite utrymme, för att få ett alternativt genomförande av en välkänd tvådimensionell räckvidd sökdatastruktur av Chazelle. Vi visar också hur Grossi et al.'s vågformade träd lämpar sig för tvådimensionell räckviddssökning, och deras koppling till Chazelles datastruktur.
Indexet O (n log n) av Mäkinen och Navarro REF kan räkna antalet händelser occ,r i O (p + log n) tid.
Position-restricted substring searching
{'venue': 'OF LECTURE NOTES IN COMPUTER SCIENCE', 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}