• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Book chapter

Cross-Document Pattern Matching

P. 196-207.
Kucherov G., Nekrich Y., Starikovskaya T.

We study a new variant of the string matching problem called {\em   cross-document string matching}, which is the problem of indexing a collection of documents to support an efficient search for a pattern in a selected document, where the pattern itself is a substring of another document. Several variants of this problem are considered, and efficient linear-space solutions are proposed with query time bounds that either do not depend at all on the pattern size or depend on it in a very limited way (doubly logarithmic). As a side result, we propose an improved solution to the {\em weighted level ancestor} problem. 

In book

Edited by: J. Karkkainen, J. Stoye. Vol. 7354: Proceedings of the 23rd Symposium on Combinatorial Pattern Matching. Berlin: Springer, 2012.