首先举个例子,
第一步:
此时,B与A的值不匹配。
第二步:
红色箭头左边的主串与模式串的元素是完全匹配的。
第三步:
模式串中有“AB”子串是相同的。
第四步:
直接移动模式串,使前缀移动到后缀的位置。
最长公共前后缀:
···前缀:不包含最后一个字符的所有以第一个字符开头的连续子串。
···后缀:不包含第一个字符的所有以最后一个字符结尾的连续子串。
第五步:
此时,B与A不匹配。
第六步:
此时,红色箭头左边的元素全部上下匹配。那么,我们开始寻找最长公共前后缀。
第七步:
此时,根据最长公共前后缀的定义,我们找到A是粉红色框作为前缀和后缀。
第八步:
此时,模式串超出主串的范围了,就可以判定匹配失败。
标签:子串,字符,匹配,前缀,后缀,算法,KMP,此时,易懂 From: https://blog.csdn.net/2401_82456039/article/details/140637585以上是KMP算法的简单理解。