字符串模式匹配算法-BF和KMP详解

#include 
#include 

using namespace std;

int BF_strMatch(vector<char> v1, vector<char> v2) {
    //v1是主串，v2是模式串
    //如果匹配成功，返回子串在主串中的起始位置；否则，返回-1；
    int i = 0, j = 0;
    int n = v1.size(), m = v2.size();
    while (i  m) {
        if (v1[i] == v2[j]) {
            ++i;
            ++j;
        }
        else {
            i = i - j + 2;//通过观察下标变换的关系得出
            j = 1;
        }
    }
    return (j == m) ? (i - m) : -1;
}


void main() {
    vector<char> s1 = { 'a','b','a','b','c','a','b','c','a','c','b','a','b'};
    vector<char> s2 = { 'a','b','c','a','c' };
    cout < endl; }

vector<int> getNext(vector<char> v) {
    //模式串str2 与 模式串str2 (自己跟自己) 做KMP匹配 
    int m = v.size();//v字符串长度
    vector<int> next(m, 0);
    int i = 2;
    int j = 0;

    if (m == 0) return next;
    next[0] = -1;
    if (m == 1) return next;
    next[1] = 0;

    while (i < m) {
        if (v[i - 1] == v[j]) {
            ++j;
            next[i] = j;
            ++i;
        }
        else if(j>0){
            j = next[j];
        }
        else {
            next[i++] = 0;
        }
        
    }
    return next;//放对位置
}

//test
void main() {
    vector<char> s3 = { 'a','b','a','a','b','c','a','c' };
    for (auto c : getNext(s3)) {
        cout <" ";
    }
    cout << endl;
}

#include 
#include 

using namespace std;

int KMP_strMatch(vector<char> v1, vector<char> v2,vector<int> next) {
    //v1是主串，v2是模式串
    //如果匹配成功，返回子串在主串中的起始位置；否则，返回-1；
    int i = 0, j = 0;
    int n = v1.size(), m = v2.size();
    while (i  m) {
        if (v1[i] == v2[j]) {
            ++i;
            ++j;
        }
        else {
            if (j == 0) ++i; //j回到模式串头部还不匹配，i加1
            j = next[j];       //使用next数组提供指导
        }
    }
    return (j == m) ? (i - m) : -1;
}

vector<int> getNext(vector<char> v) {
    //模式串str2 与 模式串str2 (自己跟自己) 做KMP匹配 
    int m = v.size();//v字符串长度
    vector<int> next(m, 0);
    int i = 2;
    int j = 0;

    if (m == 0) return next;
    next[0] = -1;
    if (m == 1) return next;
    next[1] = 0;

    while (i < m) {
        if (v[i - 1] == v[j]) {
            ++j;
            next[i] = j;
            ++i;
        }
        else if(j>0){
            j = next[j];
        }
        else {
            next[i++] = 0;
        }
        
    }
    return next;//放对位置
}


void main() {
    vector<char> s1 = { 'a','b','a','b','c','a','b','c','a','c','b','a','b'};
    vector<char> s2 = { 'a','b','c','a','c' };

    for (auto c : getNext(s2)) {
        cout <" ";
    }
    cout << endl;
    cout < endl;
}

str1:a b k a b a b k a b x str2:a b k a b a b k a b y  //i=10,j=10 不匹配，j=next[10]=5（不是j=0，减少了5次比较）,继续比较                a b k a b a b k a b F            //i=10,j=5 不匹配，j=next[5]=2（不是j=0，减少了2次比较）,继续比较
                     a b k a b a b k a b F      //i=10,j=2 不匹配，j=next[2]=0（才是j=0，较少了0次比较）,继续比较
                         a b k a b a b k a b F  //i=10,j=0 不匹配，++i（此时i才加1）,j=0

分析：
（1）加速的原因：减少了不必要的比较次数。
（2）为什么模式串可以向右滑动尽可能远一段距离后，再继续比较：

正如上面的例子：前面都是相等的，到了x与y匹配时才不相等——
 (W--------------Q)
[i|-----k---|j          |x]      //红色部分是滑过的距离，即不必要的比较次数,这里指的i……j之间的位置不可能匹配出str2
(-a-b-k-a-b)(-a-b-k-a-b)

(W--------------Q)
(-a-b-k-a-b)(-a-b-k-a-b)
[0|         |j          |y]

假设从k字符起可以配出str2，那么必然会存在更长的子串（W-------Q）比y位置的最长子串（a-b-k-a-b）更长，如果next数组求解正确，这是不可能。出现矛盾，假设不成立。
因为next数组求的就是每一个字符的最长公共子串。