• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Глава

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. 

В книге

Под науч. редакцией: J. Karkkainen, J. Stoye. Vol. 7354: Proceedings of the 23rd Symposium on Combinatorial Pattern Matching. Berlin: Springer, 2012.