模式串t=‘abcaabbabcab’,求next nextval的值

如题所述

第一位的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)。

 参考资料来源:百度百科-字符串匹配

温馨提示:答案为网友推荐,仅供参考
相似回答