KMP算法记录

发布时间 2023-12-13 11:04:44作者: qingjiawen

 

设主串T为'abaabaabcabaabc',模式串S为'abaabc'。采用KMP算法进行匹配,到匹配成功时为止,在匹配过程中进行的单个字符间的比较次数是多少次?

 

第一次匹配(有6个字符依次比较6次)

           主串T             abaabaabcabaabc

(子串)模式串S      abaabc

 

由于第一次匹配 第6个字符不匹配(移动位数=已匹配的字符数-对应的部分匹配值(对应匹配字符的长度)下标)  

得到 已匹配的字符数为5,对应的部分匹配值为 ab 长度为2

移动位数为 5-2=3.

 

           主串T              abaabaabcabaabc

(子串)模式串S            abaabc

 

第二次移位匹配 加上一次  6+1=7。前面的ab不需要匹配了所以不算次数。

 

第三次匹配 后面的 abc依次匹配 3次,一共得 6+1+3=10。

 

所以 在匹配过程中进行的单个字符间的比较次数是10次。