Window-accumulated subsequence matching problem is linear

DOI10.1016/S0168-0072(01)00051-3zbMath0998.68042MaRDI QIDQ5957906

Yu. V. Matiyasevich, Patrick Cégielski, Irène Guessarian, Luc Boasson

Publication date: 27 November 2002

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

subsequence matching

Mathematics Subject Classification ID

Searching and sorting (68P10) Database theory (68P15)

Related Items (6)

Tree inclusions in windows and slices ⋮ Multiple serial episodes matching ⋮ Tree inclusion problems ⋮ Inclusion problems in trace monoids ⋮ Compressed subsequence matching and packed tree coloring ⋮ On trace inclusion optimization problems

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for string matching with a sequence of don't cares
• Multiplication, division, and shift instructions in parallel random access machines
• Matching a set of strings with variable length don't cares
• On the power of the shift instruction
• On-line construction of suffix trees
• Real-time recognition of the inclusion relation
• String Matching in Real Time
• Fast Pattern Matching in Strings

This page was built for publication: Window-accumulated subsequence matching problem is linear