@Article{MaaNow04,
  author =	 {Moritz G. Maa{\ss} and Johannes Nowak},
  title =	 {A New Method for Approximate Indexing and Dictionary
                  Lookup with One Error},
  journal =	 ipl,
  year =	 2005,
  volume =	 96,
  number =	 5,
  month =	 dec,
  abstract =	 {We consider the problem of designing an efficient
                  index for approximate pattern matching. Despite
                  ongoing efforts, this topic is still a challenge in
                  combinatorial pattern matching. We present a new
                  data structure that allows to report all matches in
                  time linear in the pattern length and the number of
                  occurrences. Our index uses $O(n \log n)$ extra
                  space on average and with high probability, where
                  $n$ is the length of the text (indexing) or the
                  number of strings to index (dictionary lookup).}
}