Showing 2023 · cs.DSShow all
2 papers · 2 filters
cs.DS2023
Rank and Select on Degenerate Strings
Philip Bille, Inge Li Gørtz, Tord Stordalen
A 'degenerate string' is a sequence of subsets of some alphabet; it represents any string obtainable by selecting one character from each set from left to right. Recently, Alanko e…
cs.DS2023
Sliding Window String Indexing in Streams
Philip Bille, Johannes Fischer, Inge Li Gørtz +2
Given a string over an alphabet , the 'string indexing problem' is to preprocess to subsequently support efficient pattern matching queries, i.e., given a pattern string…