Inplace run-length 2d compressed search.

DOI10.1016/S0304-3975(02)00041-5zbMath1051.68059MaRDI QIDQ1401164

Amihood Amir, Dina Sokol, Gad M. Landau

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

compressed pattern matching problem

Mathematics Subject Classification ID

Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Related Items (5)

A fully compressed algorithm for computing the edit distance of run-length encoded strings ⋮ THEORETICAL ISSUES OF SEARCHING AERIAL PHOTOGRAPHS: A BIRD'S EYE VIEW ⋮ Hardness of comparing two run-length encoded strings ⋮ Approximate Matching for Run-Length Encoded Strings Is 3sum-Hard ⋮ Context-free languages can be accepted with absolutely no space overhead

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An O(n log n) algorithm for finding all repetitions in a string
• Optimal parallel pattern matching in strings
• Fast Pattern Matching in Strings
• An Alphabet Independent Approach to Two-Dimensional Pattern Matching
• Optimal Two-Dimensional Compressed Matching
• Two-Dimensional Periodicity in Rectangular Arrays
• Alphabet-Independent Two-Dimensional Witness Computation

This page was built for publication: Inplace run-length 2d compressed search.