LeetCode 28 Implement strStr()
概述
https://leetcode.com/problems/implement-strstr/
暴力法
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle == "") return 0;
for (int i = 0; i < haystack.size(); i ++) {
int k = i;
int j = 0;
for (; j < needle.size() && k < haystack.size(); j ++, k ++) {
if (haystack[k] != needle[j]) break;
}
if (j == needle.size()) {
return i;
}
}
return -1;
}
};
O(mn) 的时间复杂度，TLE 了。
离谱，下面这个就过了：
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.length()==0) return 0;
if(haystack.length()<needle.length()) return -1;
for(int i=0;i<=haystack.length()-needle.length();i++){
if(haystack[i]==needle[0]){
bool flag = true;
for(int j=1;j<needle.length();j++){
if(haystack[i+j]!=needle[j]){
flag = false;
break;
}
}
if(flag){
return i;
}
}
}
return -1;
}
};
而我参照改进的就没过：
class Solution {
public:
int strStr(string haystack, string needle) {
if (needle == "") return 0;
if (needle.size() > haystack.size()) return -1;
for (int i = 0; i <= haystack.size() - needle.size(); i ++) {
int k = i;
int j = 0;
for (; j < needle.size() && k < haystack.size(); j ++, k ++) {
if (haystack[k] != needle[j]) break;
}
if (j == needle.size()) {
return i;
}
}
return -1;
}
};
头一次见：80 / 80 test cases passed, but took too long.
这道题标的简单啊喂！
KMP 字符串匹配算法
https://labuladong.gitee.io/algo/3/26/101/
KMP 算法永不回退 txt 的指针 i，不走回头路（不会重复扫描 txt）， 而是借助 dp 数组中储存的信息把 pat 移到正确的位置继续匹配， 时间复杂度只需 O(N)，用空间换时间，所以我认为它是一种动态规划算法。
http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
大概看懂了，我们首先需要构造一个部分匹配表，其中指示了如果部分匹配到该处，我们要跳转的位置。
里面的项的计算方式：
The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.
使用方式：
If a partial match of length partial_match_length is found and table[partial_match_length] > 1, we may skip ahead partial_match_length - table[partial_match_length - 1] characters.
其实这个想法很简单，就是，当我们遇到一个不匹配的项后，我们可不可以不重置 text 指针，从该不匹配的开始呢？ 不能，因为已经匹配的那部分里可能包含新的开始，我们需要找出里面最远的新的开始，开始新的开始。 这就是为什么我们要求最大的。
举例，对于 pattern 字符串 “abababca”，我们计算部分 pattern “ababa” 时，我们有 4 个前缀：(“a”, “ab”, “aba”, and “abab”)， 和 4 个后缀：(“a”, “ba”, “aba”, and “baba”)，其中 “a” 和 “aba” 都出现了，其中 “aba” 最长，为 3， 所以对应 “ababa” 的值为 3，该部分 pattern 本身长度为 5，5 - 3 = 2，所以当我们只匹配到该部分 pattern 时， 我们可以从旧的开始 + 2 处进行新的开始，可以看到即从 aba 处开始，其显然是一个合法的已匹配部分。
实现可以参考这里： https://leetcode.com/problems/implement-strstr/discuss/12956/C%2B%2B-Brute-Force-and-KMP