International Journal of Applied Mathematical Sciences

In this paper we consider the problem of string matching algorithm based on a two-dimensional mesh. This has applications such as string databases, cellular automata and computational biology. The main use of this method is to reduce the time spent on comparisons in string matching by using mesh connected network which achieves a constant time for mismatch a text string and we obtained O(√K)-time algorithm on √K x √K meshes (K⇐n/2) from O(√n)-time algorithm on √n x √n meshes for string matching and also reduced half of the processors. This is the first known optimal-time algorithm for pattern matching on meshes.