Two-dimensional pattern matching by sampling
- Maxime Crochemore(corresponding author),
- Leszek Ga̧sieniec,
- Wojciech Rytter
- Paris-Est Sup,
- University of Warsaw,
- University of California at Riverside
Scholary Output:
Contribution to journal
Article
Peer-reviewAbstract
We extend the concept of deterministic sampling to the two-dimensional pattern matching problem. We show that almost all patterns have a logarithmic deterministic sample. There are 2D-matching algorithms which work efficiently for almost all patterns. They solve the 2D-matching problem in linear sequential time with 0(1) space, or, alternatively in 0(1) parallel time with linear number of processors. This is the first attempt to reduce the space for two-dimensional pattern matching.
Publication Information
Output type
Scholary Output:
Contribution to journal
Article
Peer-reviewOriginal language
English (US)Pages from-to (Number of pages)
Pages 159-162 (4 pages)Journal (Volume, Issue Number)
Information Processing Letters (Volume 46, Issue 4)Publication milestones
- Published - 06/25/1993
Publication status
Published - 06/25/1993
ISSN
0020-0190Publication IDs
- Scopus: 0027606840
Publication metrics
Metrics
Fractional count
1
Fractional count
0.33
Fractional count
2
Fractional count
0.67
Fractional count
1
Fractional count
1
PlumX, opens in new tab
Captures
8
Citation count
4
Funding Details
Correspondence to: M. Crochemore. Institute Gaspard Monge, 2 AlICe Jean Renoir, F-93160 Noisy-le-Grand, France. * Work by the first author is partially supported by NATO Grant CRG 900293. Work by the two other authors is supported by grant KBN 2-11-900-01.
FunderFunding numbers
NATO
CRG 900293, KBN 2-11-900-01