1. bookVolume 50 (2020): Issue 2 (June 2020)
Journal Details
License
Format
Journal
eISSN
2083-4608
First Published
26 Feb 2008
Publication timeframe
4 times per year
Languages
English
access type Open Access

An Efficient Algorithm for 2-Dimensional Pattern Matching Problem

Published Online: 22 Jun 2020
Volume & Issue: Volume 50 (2020) - Issue 2 (June 2020)
Page range: 295 - 313
Journal Details
License
Format
Journal
eISSN
2083-4608
First Published
26 Feb 2008
Publication timeframe
4 times per year
Languages
English
Abstract

Pattern matching is the area of computer science which deals with security and analysis of data. This work proposes two 2D pattern matching algorithms based on two different input domains. The first algorithm is for the case when the given pattern contains only two symbols, that is, binary symbols 0 and 1. The second algorithm is in the case when the given pattern contains decimal numbers, that is, the collection of symbols between 0 and 9. The algorithms proposed in this manuscript convert the given pattern into an equivalent binary or decimal number, correspondingly find the cofactors of the same dimension and convert these cofactors into numbers if a particular cofactor number matches indicate the matching of the pattern. Furthermore, the algorithm is enhanced for decimal numbers. In the case of decimal numbers, each row of the pattern is changed to its decimal equivalent, and then, modulo with a suitable prime number changes the decimal equivalent into a number less than the prime number. If the number mismatched pattern does not exist, the complexity of the proposed algorithm is very low as compared to other traditional algorithms.

Keywords

1. Amir A., Landau G.M., Marcus S., Sokol D.: Two-dimensional maximal repetitions. Theoretical Computer Science, 2019, DOI 10.1016/j.tcs.2019.07.006.10.1016/j.tcs.2019.07.006Search in Google Scholar

2. Amir A., Butman A., Crochemore M., Landau G.M., Schaps M.: Two-dimensional pattern matching with rotations. Theoretical Computer Science, Elsevier, 314, 2004.10.1016/j.tcs.2003.10.039Search in Google Scholar

3. Apostolico A., Giancarlo R.: The Boyer-Moore-Galil String Searching Strategies Revisited. SIAM J. COMPUT., 15, 1, 1986.Search in Google Scholar

4. Baker T.: A technique for extending rapid exact string matching to arrays of more than one dimension. SIAM Journal on Computing, 7, 3, 1978.10.1137/0207043Search in Google Scholar

5. Bayer R., Moore J.: A fast matching algorithm. ACM, 20, 10, 1977.Search in Google Scholar

6. Bird R.: Two dimensional pattern matching. Information Processing Letters, 6, 5, 1977.10.1016/0020-0190(77)90017-5Search in Google Scholar

7. Cáceres M., Puglisi S.J., Zhukova B.: Fast Indexes for Gapped Pattern Matching. In: Chatzigeorgiou A. et al. (eds.) SOFSEM 2020: Theory and Practice of Computer Science. SOFSEM 2020. Lecture Notes in Computer Science, Vol. 12011. Springer, Cham, 2020, DOI 10.1007/978-3-030-38919-2_40.Search in Google Scholar

8. Charalampopoulos P., Kociumaka T., Pissis S.P., Radoszewski J., Rytter W., Straszyński J., Waleń T., Zuba W.: Circular Pattern Matching with k Mismatches. In: Gąsieniec L., Jansson J., Levcopoulos C. (eds.) Fundamentals of Computation Theory. FCT 2019. Lecture Notes in Computer Science, Vol. 11651. Springer, Cham, 2019, DOI 10.1007/978-3-030-25027-0_15.Search in Google Scholar

9. Clifford R., Fontaine A., Starikovskaya T., Vildhøj H.W.: Dynamic and Approximate Pattern Matching in 2D. In: Proceedings of 23 International Symposium SPIRE 2016: String Processing and Information Retrieval. Lecture Notes in Computer Science, Vol. 9954. Beppu, Japan, October 18–20, 2016.Search in Google Scholar

10. Dunn W.N.: Pattern matching: Methodology. International Encyclopedia of the Social & Behavioral Sciences, 2001.10.1016/B0-08-043076-7/00756-7Search in Google Scholar

11. Karp R.M., Rabin M.: Efficient randomized pattern-matching algorithms. IBM, 31, 2, 1987.Search in Google Scholar

12. Karp R.M., Miller R.E., Rosenberg A.L.: Rapid identification of repeated patterns in strings, trees and arrays. Proceedings of the 4th Annual ACM Symposium on Theory of Computing, Assoc. for Comput. Mach., New York 1972.10.1145/800152.804905Search in Google Scholar

13. Knuth D., Morris J., Pratt V.: Fast pattern matching in strings. SIAM Journal of Computing, 6, 2, 1977.Search in Google Scholar

14. Knuth D.E., Morris J.H. Jr., Pratt V.R.: Fast pattern matching in strings. Research report, STANCS-74-440, Computer Science Department, Stanford, California 1974.Search in Google Scholar

15. Manea F., Schmid M.L.: Matching Patterns with Variables. In: Mercaş R., Reidenbach D. (eds.) Combinatorics on Words. WORDS 2019. Lecture Notes in Computer Science, Vol. 11682. Springer, Cham, DOI 10.1007/978-3-030-28796-2_1.Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo