%0 Conference Paper
%B SPIRE: String Processing and Information Retrieval
%D 2006
%T Dotted Suffix Trees: A Structure for Approximate Text Indexing
%A Luís Pedro Coelho
%A Arlindo Oliveira
%C Glasgow, Scotland
%I Springer
%K String indexing, approximate matching
%P 329--336
%S Lecture Notes in Computer Science
%U http://luispedro.org/files/dot-link.pdf
%V 4209
%X The problem we address is text indexing for approximate matching. Given a text $T$ which undergoes some preprocessing to generate an index, we can later query this index to identify the places where a string occurs up to a certain number of errors $k$ (edition distance). The indexing structure occupies space $O(n \log^k n)$ in the average case, independent of alphabet size. This structure can be used to report the existence of a match with k errors in $O(3^k m^{k+1})$ and to report the occurrences in $O(3^k m^{k+1} + ed)$ time, where $m$ is the length of the pattern and ed and the number of matching edit scripts. The construction of the structure has time bound by $O(kNS)$, where $N$ is the number of nodes in the index and $S$ the alphabet size.