Name
Abstract | ||
|---|---|---|
We describe the first worst-case efficient algorithm for simultaneously matching multiple rectangular patterns of varying sizes and aspect ratios in a rectangular text. Efficient means significantly more efficient asymptotically than applying known algorithms that handle one height (or width or aspect ratio) at a time for each height. Our algorithm features an interesting use of multidimensional range searching, as well as new adaptations of several known techniques for two-dimensional string matching. We also extend our algorithm to a dynamic setting where the set of patterns can change over time. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1006/inco.1995.1030 | Inf. Comput. |
Keywords | Field | DocType |
multiple matching,rectangular pattern,aspect ratio,string matching | String searching algorithm,Aspect ratio (image),Combinatorics,Search algorithm,Range searching,Algorithm,List processing,Pattern matching,Mathematics,Dynamic method | Journal |
Volume | Issue | ISSN |
117 | 1 | Information and Computation |
ISBN | Citations | PageRank |
0-89791-591-7 | 13 | 0.93 |
References | Authors | |
24 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ramana M. Idurys | 1 | 204 | 24.03 |
| Alejandro A. Schäffer | 2 | 827 | 136.66 |