\input zb-basic
\input zb-ioport
\iteman{io-port 05988691}
\itemau{Hon, Wing-Kai; Lu, Chen-Hua; Shah, Rahul; Thankachan, Sharma V.}
\itemti{Succinct indexes for circular patterns.}
\itemso{Asano, Takao (ed.) et al., Algorithms and computation. 22nd international symposium, ISAAC 2011, Yokohama, Japan, December 5--8, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-25590-8/pbk). Lecture Notes in Computer Science 7074, 673-682 (2011).}
\itemab
Summary: Circular patterns are those patterns whose circular permutations are also valid patterns. These patterns arise naturally in bioinformatics and computational geometry. In this paper, we consider succinct indexing schemes for a set of $d$ circular patterns of total length $n$, with each character drawn from an alphabet of size $\sigma $. Our method is by defining the popular Burrows-Wheeler transform (BWT) on circular patterns, based on which we achieve succinct indexes with space $n \log \sigma (1 + o(1)) + O(n) + O(d\log n)$ bits, while pattern matching or dictionary matching queries can be supported efficiently.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-25591-5\_69}
\end