Cross-document pattern matching

DOI10.1007/978-3-642-31265-6_16MaRDI QIDQ2904492zbMATH OpenOpenAlexWikidataFDO

Authors Gregory Kucherov, Yakov Nekrich, Tatiana Starikovskaya

Publication date 14 August 2012

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

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

Mathematics Subject Classification ID

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

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.

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

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)