设主串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次。