KMP和朴素匹配BF

  1. KMP和朴素匹配算法BF

class Solution {
public:
    int kmp(string ts, string ps) {
        int i = 0;
        int j = 0;
        vector<int> next(ps.size());
        get_next(ps, next);
        while (i < (int) ts.size() && j < (int) ps.size()) {//string::size()返回的是一个无符号的整数,当与负数比较会出错
            if (j == -1 || ts[i] == ps[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        if (j == ps.size())
            return i - j;
        else
            return -1;
    }

    void get_next(string ps, vector<int> &next) {
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < (int) ps.size() - 1) {
            if (k == -1 || ps[j] == ps[k]) {
                next[++j] = ++k;
            } else
                k = next[k];
        }
    }

    int bf(string ts, string ps) {//朴素搜索
        int i = 0;
        int j = 0;
        while (i < (int) ts.size() && j < (int) ps.size()) {
            if (ts[i] == ps[j]) {
                i++;
                j++;
            } else {
                i = i - j + 1;//回溯
                j = 0;
            }
        }
        if (j == (int) ps.size())
            return i - j;
        else
            return -1;
    }
};

2.KMP原理

寻找最长前缀后缀

假设现在文本串S匹配到 i 位置,模式串P匹配到 j 位置

  • 如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++,继续匹配下一个字符;
  • 如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j – next [j] 位。
    • 换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 – 失配字符对应的next 值,即移动的实际位数为:j – next[j],且此值大于等于1。

字符串查找之KMP

0