一种模式匹配快速算法

A Fast String-matching Algorithm

在定义模式串的特征值之后,给出了判断两等长串匹配的必要条件以及两相邻子串的特征值之间的递推关系。在此基础上,提供一种模式匹配快速算法,其时间复杂度可达O(n)。该算法彻底避免了回溯现象,执行效率要比RK算法高。

After introducing the definition of a string＇s eigenvalue ,necessary conditions used to judge if two strings having equal lengths are matched, and a recurrence relation between the eigenvalues of two adjacent substrings are given. Then a fast string-matching algorithm which expected running time is O（n） is presented. The algorithm is more effective than RK algorithm and avoiding all backtrackings thoroughly.