KMP应用求两个字符串的最长公共子串

问题描述:

求解两个字符串的最长公共子串

问题解决:

使用KMP算法,求解字符串的最长公共子串

具体实现:

    第一步:选取长度较短的子串作为匹配串,较长的字符串作为母串

    第二步:截短子串匹配较长的字符串,记录匹配长度的最大值以及匹配开始的位置

    第三步:返回或者输出匹配长度最长的公共子串

(1)构造Next数组,记录匹配串的回溯位置

clipboard

(2)找出每一个子串进行匹配,记录每一个子串匹配成功的长度以及匹配成功的位置,从所有匹配成功的长度中选取最大长度以及对应的位置

clipboard

clipboard

原文地址:https://www.cnblogs.com/luosongchao/p/3051077.html