The two-dimensional pattern matching problem finds the occurrences of a given two-dimensional pattern array in a two-dimensional text array. The paper presents two efficient algorithms, which combine Fan-Su (1993) and Aho-Corasick (1979) string search algorithms, to solve this problem. The proposed algorithms need not inspect each character of the text array during the pattern matching in most cases. Additionally, unlike the algorithms proposed by Zhu and Takaoka (1989) which are based on the hashing method, these new algorithms require no preprocessing of the text array. A comparison of the performance of various algorithms is presented. The result shows that the proposed algorithms are about three to six times faster than the best algorithm proposed previously when the size of the pattern array is less than 1/100 of the size of the text array, which occurs frequently in many applications.>

An efficient algorithm for performing multiple pattern match in a string is described. The match algorithm combines the concept of deterministic finite state automata (DFSA) and the Boyer-Moore algorithm to achieve better performance. Experimental results indicate that in the average case, the algorithm is able to perform pattern match operations sublinearly, i.e. it does not need to inspect every character of the string to perform pattern match operations. The analysis shows that the number of characters to be inspected decreases as the length of patterns increases, and increases slightly as the total number of patterns increases. To match an eight-character pattern in an English string using the algorithm, only about 17% of all characters of the strong and 33% of all characters of the string, when the number of patterns is seven, are inspected. In an actual testing, the algorithm running on SUN 3/160 takes only 3.7 s to search seven eight-character patterns in a 1.4-Mbyte English text file.>