Cross-document pattern matching

DOI10.1007/978-3-642-31265-6_16zbMATH Open1358.68094arXiv1202.4076OpenAlexW3106192328WikidataQ58064485 ScholiaQ58064485MaRDI QIDQ2904492FDOQ2904492

Authors: Gregory Kucherov, Yakov Nekrich, Tatiana Starikovskaya 

Publication date: 14 August 2012

Published in: Combinatorial Pattern Matching (Search for Journal in Brave)

Abstract: We study a new variant of the string matching problem called 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 weighted level ancestor problem.

Full work available at URL: https://arxiv.org/abs/1202.4076

Recommendations

• Cross-document pattern matching
• scientific article; zbMATH DE number 2119724
• Space-Efficient Algorithms for Document Retrieval
• Forbidden patterns
• On Hardness of Several String Indexing Problems

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Algorithms on strings (68W32)

Cited In (2)

• Cross-document pattern matching
• Fast algorithm for partial covers in words

This page was built for publication: Cross-document pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2904492)