A Technique for Two-Dimensional Pattern Matching.

This article presents information related to a pattern matching algorithm for a two-dimensional case which is a combination of the KMP and RK algorithms. The KMP algorithm solves the problem by comparing the characters of the pattern with those of the text from the left end of the pattern. Since the text pointer points to the character b, which does not match a in the pattern, the pattern is shifted one place to the right and the next text character is inspected. Computer experiments show that for various pattern sizes the average cost for either of the algorithms is much less than that of the B algorithm. The RK algorithm solves the problem by treating each possible M-character section of the text as a key in a hash table, then computing the hash function of it and checking to see if it is equal to the hash function of the pattern. The general scheme of the algorithm is to use the hash function method proposed in the RK algorithm vertically. The procedure KMP only works because the KMP algorithm is independent of the size of the character alphabet, which can consequently be arbitrarily large.