Efficient Algorithm for Two Dimensional Pattern Matching Problem (Square Pattern)
Hussein Abu-Mansour, Jaber Alwidian, Wael Hadi
International Journal of Computational Linguistics Research, Vol. 3, No. 2, 2012.
DOI: 
Link: http://www.dline.info/jcl/fulltext/v3n2/3.pdf
Abstract:
In recent decades, our computers tolerate multidimensional data to be stored and maintained depending on the high computational strength of these computers. As a result, the two-dimensional pattern matching considered as one of the hot research areas. In this paper, we investigate the exact two dimensional pattern matching problem. A new algorithm to solve the main problem in this field is proposed which converts the two dimensional problem into one dimensional problem before searching process which required high computational cost in preprocessing phase. The proposed algorithm deals with white and black images, specifically, with text images. Experimental results show the superiority of the proposed algorithm when comparing with (Brute-force algorithm, RK-KMP algorithm). The results of our algorithm point to the number of comparisons have been reduced in many cases. In another side, when we apply the proposed algorithm on one dimensional text, its time is proportional to &#952; (n), that means our time in this case is linear.