字符串匹配,leetcode28题。时间复杂度O(MN)的算法大家都会,题解里面官方账号给出的利用字符串哈希判等的O(N)算法也很优秀。本篇的重点是KMP算法。
网上能搜到的KMP算法例子非常多,其原理可以看视频,其实就是利用了一段字符串的相同前缀后缀。
如果还不是很好理解,可以看labuladong的题解。一个KMP算法易理解版本,讲解的部分也很清楚。
本篇主要是对此题解做一个补充,个人感觉题解中对“影子状态”,X的表述不是很清楚,原题解说的是所谓影子状态,就是和当前状态具有相同的前缀。
其实此题解里面的X,就是原KMP算法里,字符串具有相同前缀后缀的子字符串的前缀下标(好像有点绕)。就借用题解里面的例子吧,例如下图。为什么j = 4的时候,X = 3呢?其实就是因为在ABAB这个字符串中,长度为2的前缀和长度为2的后缀是相同的(都是AB)。
同理,为什么j = 3的时候,X = 1呢?就是因为字符串ABA中,长度为1的前缀和长度为1的后缀是相同的,这就吻合了KMP算法。
题解中,个人感觉比较难想到的难理解的是对“影子索引”更新的那一句代码,即X = dp[X][needle[idx]];其实带入我们上面对X意义的说明,就很清楚了,这句代码其实就是与当前字符串后缀相同的前缀长度是X,遇到字符 pat[j],那么如果后缀加上pat[j],与后缀相同的前缀长度是多少?换言之,该定位到 哪里去?(比如是0的话,那么就没有这样的前缀)。
对X的解释我们都清楚了。再说一点我个人对KMP算法的思考,之所以它相比于暴力解法能获得加速,就在于假如当前匹配到的位置没有与后缀相同的前缀的话,我们就不必再在这里匹配的,不可能匹配的。比如这个例子
KMP算法会不会漏解呢?只需要跑一下例子pattern = “aaaaf”,target = "xxxxxxaaaaaf",看一下对于pattern中每个位置,X的值是多少就可以理解,不会有漏掉的解。
完整代码:
int strStr(string haystack, string needle) {
int len_1 = haystack.size();
int len_2 = needle.size();
if(len_1 < len_2) return -1;
if(len_2 == 0) return 0;
//构造DP数组的部分
vector<vector<int>> dp(len_2,vector<int>(256,0));
dp[0][needle[0]] = 1;
int X = 0;
for(int idx = 1;idx < len_2;idx++){
for(char ch = 'a';ch <= 'z';ch++)
dp[idx][ch] = dp[X][ch];
dp[idx][needle[idx]] = idx + 1;
X = dp[X][needle[idx]];
}
//开始匹配了
int j = 0;
for(int idx = 0;idx < len_1;idx++){
j = dp[j][haystack[idx]];
if(j == len_2) return idx - (len_2 - 1);
}
return -1;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)