Summary: Let \(T\) be a text of length \(n\) containing characters from an alphabet \(\Sigma\), which is the union of two disjoint sets: \(\Sigma_s\) containing static characters \((s\)-characters) and \(\Sigma_p\) containing parameterized characters \((p\)-characters). Each character in \(\Sigma_p\) has an associated complementary character from \(\Sigma_p\). A pattern \(P\) (also over \(\Sigma)\) matches an equal-length substring \(S\) of \(T\) iff the \(s\)-characters match exactly, there exists a one-to-one function that renames the \(p\)-characters in \(S\) to the \(p\)-characters in \(P\), and if a \(p\)-character \(x\) is renamed to another \(p\)-character \(y\) then the complement of \(x\) is renamed to the complement of \(y\). The task is to find the starting positions (occurrences) of all such substrings \(S\). Previous indexing solution T. Shibuya [Lect. Notes Comput. Sci. 1851, 393–406 (2000; Zbl 0966.68508)], known as Structural Suffix Tree, requires \(\Theta(n\log n)\) bits of space, and can find all occ occurrences in time \(O(|P|\log\sigma+\mathrm{occ})\), where \(\sigma=|\Sigma|\). In this paper, we present the first succinct index for this problem, which occupies \(n\log\sigma+O(n)\) bits and offers \(O(|P|\log\sigma+\mathrm{occ}\cdot\log n\log\sigma)\) query time.
For the entire collection see [Zbl 1376.68013].