第一位的next值为0,第二位的next值为1,后面求解每一位的next值时,根据前一位进行比较。将前一位与其next值对应的内容进行比较,如果相等,则该位的next值就是前一位的next值加上1。
如果不等,向前继续寻找next值对应的内容来与前一位进行比较,直到找到某个位上内容的next值对应的内容与前一位相等为止,则这个位对应的值加上1即为需求的next值,如果找到第一位都没有找到与前一位相等的内容,那么需求的位上的next值即为1。
求第三位next值时看前一位(序号为2)b(都和这个b比较),next值为1,则看序列号为1对应是a与b不相同,没有再之前的数,所以第三位next值是1。
扩展资料:
注意事项:
1、在求next函数值与nextval值时,要得出前缀串和后缀串的最长相同串。
2、字符串匹配中( )用于保存字符串,[ ]用于定义匹配的字符范围,{ }用于表示匹配的长度。
3、如果相同则 i, j 分别+1, 继续比较 S[1] 和 T[1]. (例子中 S[1] = T[1] = b)。
4、直到出现不相同S[i] != T[j]. (例子中 S[2] = c != T[2] = d)。
参考资料来源:百度百科-字符串匹配