Title: Fast Incremental Text Editing
Authors: Paolo Ferragina* and Roberto Grossi**

*  University of Pisa, Italy. E-mail: ferragin@di.unipi.it.
** University of Florence, Italy. E-mail: grossi@di.unipi.it.


Exact pattern matching on strings is the basic problem of determining  all
the occurrences of a pattern string $P$, of length $p$, as a  substring of
a larger text string $T$, of length $n$.   The pattern matching is called
``on-line'' when the text $T$ is given in advance to be preprocessed, with
no knowledge about the subsequent pattern queries. Having preprocessed the
text, the cost of querying $P$ is expected to be proportional only to its
length $p$ and to the number $pocc$ of its occurrences in $T$, and hence
as much as independent of $n$ (which can be prohibitively large compared
to $p$ and $pocc$). However, in a more realistic situation --- such as in
a text editor that supports incremental searches (e.g., the command
`isearch-forward' in Gnu Emacs) --- the incremental editing of the text is
interleaved with on-line queries of the patterns. 

We propose novel data structures and fast algorithmic techniques to solve
the Incremental Text Editing Problem, in which the on-line pattern
matching is performed into a text subject to ``incremental'' insertions
and deletions of strings. Our algorithms improve previous known bounds,
and are based upon combinatorial properties of ``chains'' of pattern
occurrences in the text. We exploit a geometric interpretation and
introduce the Dynamic Suffix Array, which is the first dynamic data
structure that combines the flexibility of Suffix Trees [McCreight, 1976]
with the lexicographic order of Suffix Arrays [Manber and Myers, 1993].