邻间关系匹配算法研究

Neighbor Relationship-Based String Matching Algorithm

对于26个字母的全排,它们的邻间关系是唯一的。文中根据这个特性,针对子串长度较长的(大于26)字符串匹配问题,提出了一种基于邻间关系的匹配算法。该算法把字符串的邻间关系转化为十进制的数值,并利用这一数值实现字符串的快速匹配。该算法时间复杂度为О(m-n),且算法简便,容易实现。

Giving the arrangement of twenty- six letters, the sequence is exclusive, and the neighbor relationship of the lettes in the se quenee is a fixed value. Taking advantage of the feature given above, presents a string matching algorithm based on neighbor relationship, to solve the question of long string matching （more than twenty - six）. The algorithm transforms the neighbor relationship to a value, and achieves the fast string matching by using this value. The time complexity of the algorithm is O（ m - n ）. By the way, this algorthm has the feature of simplicity and convenience, and it is easy to realize.