为什么使用KMP

解决问题：在主串“SSSSSSSSSSSSSSSSSSSSSSSA”中查找”SSB”，比较到最后一个才知道不匹配，然后回溯，效率低。

KMP优势

分析子串n本身的特点（生成next数组），在主串m查找子串的时候，不需要重头遍历，从有重复部分的地方开始遍历即可。时间复杂度：O(m+n)

暴力查找遍历的时间复杂度：O(mn)

如何使用KMP

生成next数组

生成next数组最重要的就是：前缀和后缀相同的字符个数（找到相同个数的字符串，后面使用KMP回溯时，就可以快速回溯到特征字符串，避免每次都回溯到第一个字符）

什么是前后缀

将字符串从中间一分为二，前面为前缀，后面为后缀。
举例：
“ABCDABC”前缀为“ABC”，后缀也为“ABC”
“ABCD”前缀为“AB”，后缀为“CD”
next数组就是存放的到j位置，前后缀相同字符的个数。
举例：
“ABCDABC”
next[] = {0，0，0，0，1，2，3}
其中取next[5]为例
截取字符：ABCDAB，其中前缀“ABC”和后缀“DAB”有相同字符“AB”，长度为2，即next[5] = 2。

生成next数组代码如下

void findNext(std::vector<int>& next, std::string pattern) {
    int i = 1, j = 0;
    while (i < pattern.length()) {
        if (pattern[i] == pattern[j]) {
            j++;
            next[i] = j;
            i++;
        }
        else if (j == 0) {
            next[i] = 0;
            i++;
        }
        else {
            j = next[j-1];
        }
    }
}

KMP使用

将主串（下标i）和子串（下表j）进行比较。
i一直递增。
如果主串下标i处与子串下标j处相同，则j递增；
否则j回溯到next[j-1]处。
因为next是存放的是：截至到下标处相同的字符串个数。所以j要回溯到next[j-1]处。
举例
主串：“ABABCABABD”
子串：“ABABD”
i = 4, j = 4时，字符串不相同，此时j需要开始回溯。
原理：
第一次匹配j之前有n个相同的字符（后缀）；
第二次匹配的时候，就取子串前n个字符（前缀）。
这也是为什么要找前后相同的字符串个数的原因。

KMP实现代码

int search(std::string text, std::string pattern, std::vector<int> next) {
    int i = 0, j = 0;
    while ( i < text.length() && j < pattern.length()) {
        if (text[i] == pattern[j]) {
            if (j == pattern.length() - 1) {
                return i - (pattern.length() - 1);
            }
            i++;
            j++;
        }
        else if (!j) {
            i++;
        }
        else {
            j = next[j - 1];
        }
    }
    return -1;
}

测试用例

寻找主串中子串位置。

void main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";
    std::vector<int> next(pattern.length());
    findNext(next, pattern);
    int positions = search(text, pattern, next);
    std::cout << positions;
}

214最短回文串

int search(std::string text, std::string pattern, std::vector<int> next) {
    int i = 0, j = 0;
    while (i < text.length() && j < pattern.length()) {
        if (text[i] == pattern[j]) {
            if (j == pattern.length() - 1) {
                return pattern.length();
            }
            i++;
            j++;
        }
        else if (!j) {
            i++;
        }
        else {
            j = next[j - 1];
        }
    }
    return j;
}

void findNext(std::vector<int>& next, std::string pattern) {
    int i = 1, j = 0;
    while (i < pattern.length()) {
        if (pattern[i] == pattern[j]) {
            j++;
            next[i] = j;
            i++;
        }
        else if (j == 0) {
            next[i] = 0;
            i++;
        }
        else {
            j = next[j-1];
        }
    }
}
void main() {
    std::string s = "abcd";
    std::vector<int> next(s.length());
    findNext(next, s);
    std::string s2 = s;
    std::reverse(s2.begin(), s2.end());
    int positions = search(s2, s, next);
    std::cout << positions;
}

KMP算法详解