SDFA： a Uniform Model for String Matching Algorithms

String matching algorithms play an important role in computer science. However, there is no uniform mathematical model to describe these algorithms. Thus, read-head-Skippable DFA (SDFA) is put forward, which is an extension of two-way DFA. It is proved that SDFA is equivalent to DFA. Furthermore, SDFA is a more natural mathematical model for string matching algorithms. After that, four types of the movement of the read head of string matching are analyzed and modeled by SDFA. Finally, the SDFA model of BMA string matching algorithms is given.