网页免费模板下载,网站关键词优化互点,深圳公司网站建设哪里专业,常德建设工程信息网我们为什么需要KMP#xff1f;
在字符串匹配问题中#xff0c;我们需要找到匹配串pattern在原串text中的位置#xff0c;一种显而易见的思路就是暴力匹配#xff0c;如图所示#xff0c;我们把pattern放置到text中的每个位置进行比较即可。 但是大家可以发现#xff0c;…我们为什么需要KMP
在字符串匹配问题中我们需要找到匹配串pattern在原串text中的位置一种显而易见的思路就是暴力匹配如图所示我们把pattern放置到text中的每个位置进行比较即可。 但是大家可以发现这种方式的时间复杂度太高了达到了O(pattern.length * text.length)我们是否可以进一步进行优化呢在第一次匹配时abaa和abab的最后一个字符不匹配前面aba都匹配好了移动了一位之后发现前面又匹配不上了这次移动相当于多此一举。换句话说我们每次移动应当让前面仍然保持匹配状态直接比较后面的位置。
本例中应当直接移动两位让aaab和abaa比较这也就是KMP的基本思想了。
基础知识 求匹配数组maxMatchLens
那么我们如何做到在移动的过程中保证前面的匹配状态呢下图可以清晰地描述 发生匹配错误的字符为c左端为abab在移动的时候要保证真前缀和真后缀相等且长度最大选了较小的会忽略可能正确的结果对于abab 真前缀a ab aba 真后缀b ab bab 也就是说我们需要找到pattern中所有位置相匹配的真前缀与真后缀中最长的字符串的长度这也就是我们经常听到的next数组了这里我们用maxMatchLens来表示如下图所示的例子中假设我们已经求出来前面所有的值了最后一个值如何求解呢 举例 第五位 c
c各参数取值Value c1Value c2Value c3currentLen210pattern.charAt(currentLen)abai444pattern.charAt(i)ccc处理1.while字符不相等1.while字符不相等3.赋值 maxMatchLens[4] currentLen0;
private int[] getMaxMatchLens(String pattern) {int[] maxMatchLens new int[pattern.length()];int currentLen 0;for (int i 1; i pattern.length(); i) {while (currentLen 0 pattern.charAt(i) ! pattern.charAt(currentLen)) {currentLen maxMatchLens[currentLen - 1];}if (pattern.charAt(i) pattern.charAt(currentLen)) {currentLen;}maxMatchLens[i] currentLen;}return maxMatchLens;
}
KMP匹配
返回起始坐标 text里面找pattern 匹配的思路与求maxMatchLens的思路基本一致即按照最长、次长的顺序进行移位匹配代码如下 private ListInteger search(String text, String pattern) {ListInteger res new ArrayList();int[] maxMatchLens getMaxMatchLens(pattern);int j 0;for (int i 0; i text.length(); i) {while (j 0 text.charAt(i) ! pattern.charAt(j)) {j maxMatchLens[j - 1];}if (pattern.charAt(j) text.charAt(i)) {j;}if (j pattern.length()) {res.add(i - j 1);j maxMatchLens[j - 1];}}return res;
}
参考链接https://leetcode-cn.com/problems/longest-happy-prefix/solution/ni-zhen-de-li-jie-kmpma-jiao-ni-xun-su-zhang-wo-bi/ 参考链接https://blog.csdn.net/V_0617/article/details/79114860
