TY - GEN

T1 - Efficient algorithm for dynamic text indexing

AU - Gu, Ming

AU - Farach, Martin

AU - Beigel, Richard

PY - 1994

Y1 - 1994

N2 - Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up. All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.

AB - Text indexing is one of the fundamental problems of string matching. Indeed, the suffix tree, the central data structure of string matching, was developed as an efficient static text indexer. The text indexing problem is that of building a data structure on a text which allows the occurrences of patterns to be quickly looked up. All previous text indexing schemes have been static in the sense that if the text is modified, the data structure must be rebuilt from scratch. In this paper, we present a first dynamic data structure and algorithms for the On-line Dynamic Text Indexing problem. Our algorithms are based on a novel data structure, the border tree, which exploits string periodicities.

UR - http://www.scopus.com/inward/record.url?scp=0028197844&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0028197844&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0028197844

SN - 0898713293

T3 - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

SP - 697

EP - 704

BT - Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms

PB - Publ by ACM

T2 - Proceedings of the Fifth Annual SIAM Symposium on Discrete Algorithms

Y2 - 23 January 1994 through 25 January 1994

ER -