KMP
KMP的主要思想是当出现字符串不匹配时，可以知道一部分之前已经匹配的文本内容，可以利用这些信息避免从头再去做匹配了。
前缀表：起始位置到下标i之前（包括i）的子串中，有多大长度的相同前缀后缀。
那么使用KMP可以解决两类经典问题：
再一次强调了什么是前缀，什么是后缀，什么又是最长相等前后缀。
最长公共前后缀
前缀：指不包含最后一个字符的所有以第一个字符开头的连续子串。
后缀：指不包含第一个字符的所有以最后一个字符结尾的连续子串。
然后针对前缀表到底要不要减一，这其实是不同KMP实现的方式，我们在KMP精讲 (opens new window)中针对之前两个问题，分别给出了两个不同版本的的KMP实现。
其中主要理解j=next[x]这一步最为关键！
时间复杂度分析
其中n为文本串长度，m为模式串长度，因为在匹配的过程中，根据前缀表不断调整匹配的位置，可以看出匹配的过程是O(n)，之前还要单独生成next数组，时间复杂度是O(m)。所以整个KMP算法的时间复杂度是O(n+m)的。
暴力的解法显而易见是O(n × m)，所以KMP在字符串匹配中极大地提高了搜索的效率。
前缀表不减一来构建next数组，代码如下：
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
while (j > 0 && s[i] != s[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
}
if (s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
构建完next数组后，对字符串匹配的实现代码如下：
class Solution {
public:
void getNext(int* next, const string& s) {
int j = 0;
next[0] = 0;
for(int i = 1; i < s.size(); i++) {
while (j > 0 && s[i] != s[j]) {
j = next[j - 1];
}
if (s[i] == s[j]) {
j++;
}
next[i] = j;
}
}
int strStr(string haystack, string needle) {
if (needle.size() == 0) {
return 0;
}
int next[needle.size()];
getNext(next, needle);
int j = 0;
for (int i = 0; i < haystack.size(); i++) {
while(j > 0 && haystack[i] != needle[j]) {
j = next[j - 1];
}
if (haystack[i] == needle[j]) {
j++;
}
if (j == needle.size() ) {
return (i - needle.size() + 1);
}
}
return -1;
}
};
- 时间复杂度: O(n + m)
- 空间复杂度: O(m)