Abstract
Two equal length strings, or two equal sized two dimensional texts, parameterize match (p-match) if there is a one-one mapping (relative to the alphabet) of their characters. Two dimensional parameterized matching is the task of finding all m × m substrings of an n× n text that p-match to an m× m pattern. This models, for example, searching for color images with changing of color maps. We present an algorithm that solves the two dimensional parameterized matching problem in O(n 2+m 2.5·polylog(m)) time.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alon, N., Naor, M.: Derandomization, witnesses for boolean matrix multiplication and construction of perfect hash functions. Algorithmica 16, 434–449 (1996)
Amir, A., Aumann, Y., Cole, R., Lewenstein, M., Porat, E.: Function matching: Algorithms, applications and a lower bound. In: Baeten, J.C.M., Lenstra, J.K., Parrow, J., Woeginger, G.J. (eds.) ICALP 2003. LNCS, vol. 2719, pp. 929–942. Springer, Heidelberg (2003)
Amir, A., Benson, G., Farach, M.: An alphabet independent approach to two dimensional pattern matching. SIAM J. on Computing 23(2), 313–323 (1994)
Amir, A., Church, K.W., Dar, E.: Separable attributes: a technique for solving the submatrices character count problem. In: Proc. 13th Symposium on Discrete Algorithms (SODA), pp. 400–401 (2002)
Amir, A., Cole, R.: Personal communications (2004)
Amir, A., Farach, M., Muthukrishnan, S.: Alphabet dependence in parameterized matching. Information Processing Letters 49, 111–115 (1994)
Apostolico, A., Erdös, P., Lewenstein, M.: Parameterized matching with mismatches (manuscript)
Babu, G.P., Mehtre, B.M., Kankanhalli, M.S.: Color indexing for efficient image retrieval. Multimedia Tools and Applications 1(4), 327–348 (1995)
Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proc. 25th ACM Symposium on the Theory of Computation (STOC), pp. 71–80 (1993)
Baker, B.S.: Parameterized string pattern matching. J. Comput. Systems Sci. 52(1), 28–42 (1996)
Baker, B.S.: Parameterized duplication in strings: Algorithms and an application to software maintenance. SIAM J. on Computing 26(5), 1343–1362 (1997)
Cole, R., Hariharan, R.: Faster suffix tree construction with missing suffix links. In: Proc. 32nd ACM Symposium on the Theory of Computation (STOC), pp. 407–415 (2000)
Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th ACM Symposium on Theory of Computing (STOC), vol. 67, pp. 135–143 (1984)
Gupta, P., Janardan, R., Smid, M.: Further results on generalized intersection searching problems: Counting, reporting, and dynamization. J. of Algorithms 19(2), 282–317 (1995)
Hazay, C., Lewenstein, M., Sokol, D.: Approximate parameterized matching. In: Albers, S., Radzik, T. (eds.) ESA 2004. LNCS, vol. 3221, pp. 414–425. Springer, Heidelberg (2004)
Kosaraju, S.R.: Faster algorithms for the construction of parameterized suffix trees. In: Proc. 36th Symposium on Foundation of Computer Science (FOCS), pp. 631–637 (1995)
Swain, M., Ballard, D.: Color indexing. International Journal of Computer Vision 7(1), 11–32 (1991)
Vishkin, U.: Optimal parallel pattern matching in strings. In: Brauer, W. (ed.) ICALP 1985. LNCS, vol. 194, pp. 91–113. Springer, Heidelberg (1985)
Vishkin, U.: Deterministic sampling — a new technique for fast pattern matching. SIAM J. on Computing 20, 303–314 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Hazay, C., Lewenstein, M., Tsur, D. (2005). Two Dimensional Parameterized Matching. In: Apostolico, A., Crochemore, M., Park, K. (eds) Combinatorial Pattern Matching. CPM 2005. Lecture Notes in Computer Science, vol 3537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496656_23
Download citation
DOI: https://doi.org/10.1007/11496656_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26201-5
Online ISBN: 978-3-540-31562-9
eBook Packages: Computer ScienceComputer Science (R0)