LeetCode28 实现strStr() -- KMP算法

链接： https://leetcode-cn.com/problems/implement-strstr/

题面

给定pattern和text，进行字符串的匹配

解法

经典的KMP算法
用O(m+n)的时间完成字符串的匹配
需要用到一个prefix数组，预处理所有前缀和后缀。
对于长度为$m$的字符串$s$，其前缀函数$ \pi(i)(0 \leq i < m)$表示$s$的子串$s[0:i]$的最长的相等的前缀与后缀的长度。

在真正进行匹配的时候就要用到这个prefix数组
具体用到的地方是会在当出现字符不匹配的时候不需要从头开始找起
而会“跳到”上一个匹配的地方进行下一次的匹配
结合代码进行理解

代码

class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;
        int m = haystack.size(), n = needle.size();
        vector<int> prefix(n); // 计算prefix数组
        for (int i = 1, j = 0; i < n; i++) {
            if (needle[i] == needle[j]) {
                prefix[i] = j + 1;
                j++;
            }
            else {
                while (j != 0) {
                    j = prefix[j - 1];
                    if (needle[i] == needle[j]) {
                        break;
                    }
                }
                if (needle[i] == needle[j]) {
                    prefix[i] = j + 1;
                    j++;
                }
            }
        }
        // 开始kmp匹配
        for (int i = 0, j = 0; i < m; i++) {
            if (haystack[i] == needle[j]) {
                j++;
                if (j == n) return i - n + 1;
            }
            else {
                if (j != 0) {
                    j = prefix[j - 1];
                    i--;
                }
            }
        }
        return -1;
    }
};