数据结构,串的模式匹配的一个小疑问

对软考《程序设计师》中级教材上的一点疑问:
图片描述

最坏情况下,每一趟不成功的匹配都是模式串的最后一个字符,与主串中相应的字符不相等,则主串中新一趟的起始位置为 i-m+2。

这个 i-m+2 是怎么来的?
按照朴素的串匹配算法,比较不成功,下一趟的起始位置,应该是主串的下一个字符啊。

假设主串为S,长度为n,模式串为P,长度为m。
首先从S[0]开始,逐位比较S和P
如果匹配失败,就从S[1]开始,然后S[2]S[3]...

阅读 1.7k
1 个回答

这里边的i的含义应该是:最坏情况下,与模式串匹配失败的主串位置下标。