@inproceedings{8097f29c29ca4795b7a2b5510c023e4b,
title = "Adaptive dictionary matching",
abstract = "Semiadaptive and fully adaptive dictionary matching algorithms are presented. In the fully adaptive algorithm, the dictionary is processed in time O(|D| log |D|). Inserting a new pattern Pk+1 into the dictionary can be done in time O |PK+1| log |D|). A dictionary pattern can be deleted in time O(log |D|). Text scanning is accomplished in time O(|T| log |D|). Also presented is a parallel version of the algorithm with optimal speedup for the dictionary construction and pattern addition phase and a logarithmic overhead in the text scan phase. The method used incorporates a new way of using suffix trees as well as a new data structure in which the suffix tree is embedded for the sequential algorithm.",
author = "Amihood Amir and Martin Farach",
year = "1991",
month = dec,
language = "English (US)",
isbn = "0818624450",
series = "Annual Symposium on Foundations of Computer Science (Proceedings)",
publisher = "Publ by IEEE",
pages = "760--766",
booktitle = "Annual Symposium on Foundations of Computer Science (Proceedings)",
note = "Proceedings of the 32nd Annual Symposium on Foundations of Computer Science ; Conference date: 01-10-1991 Through 04-10-1991",
}