BF算法

朴素做法, 简单粗暴, 易于理解

平均时间复杂度$O(n + m)$

最坏时间复杂度$O(n * m)$

int index_BF(string s, string t, int pos){
    int i = pos, j = 1;
    while(i <= s.length() && j <= t.length()){
        if(s[i] == t[j]) ++ i, ++ j;
        else i = i - j + 2, j = 1;
    }
    if(j > t.length()) return i - t.length();
    return 0;
}

公共前后缀

公共前后缀的条件：
1. 最长的公共前后缀
2. 不包含字符串本身

KMP算法

BF改进算法,同样易于实现, 重点在于next函数的设计.

时间复杂度$O(n + m)$

KMP算法 — 模板1

next[i] = j的含义为：
含义1. 模板串第 i 个字母与主串对应字母不匹配时,模板串下一个要与主串对应字母匹配的位置为 j
含义2. next[i] = j, 表示 t[1, j - 1] = t[i - j + 1, i - 1], 即以 i 结尾的最长公共前后缀的长度为 j - 1

next函数

void get_next(string t, int next[]){
    int i = 1, j = 0;
    ne[1] = 0;
    while(i <= t.length()){//得包括计算ne[n + 1]的值,也可以不计算ne[n + 1]
        if(j == 0 || t[i] == t[j]) ++ j, ++ i, ne[i] = j;
        else j = ne[j];
    }
}

改进后的next函数

void get_next(string t, int next[]){
    int i = 1, j = 0;
    ne[1] = 0;
    while(i <= t.length()){//得包括计算ne[n + 1]的值, 
        if(j == 0 || t[i] == t[j]){
            ++ j, ++ i;
            if(t[i] != t[j]) ne[i] = j;
            else ne[i] = ne[j];
        }
        else j = ne[j];
    }
}

KMP算法 ---- 成功匹配一次后结束

int  index_kmp(string s, string t, int pos){
    int i = pos, j = 1;
    while(i <= s.length() && j <= t.length()){
        if(j == 0 || s[i] == t[j]) ++ i, ++ j;
        else j = ne[j];
    }
    if(j > t.length()) return i - t.length();
    return 0;
}

KMP算法 ---- 成功匹配多次后结束

void kmp(string s, string t, int pos){
    int i = pos, j = 1;
    while(i <= s.length() && j <= t.length()){
        if(j == 0 || s[i] == t[j]) ++ i, ++ j;
        else j = ne[j];
        if(j > t.length(){//匹配成功
            cout << i - t.length() << ' ';//输出第一次匹配成功的位置
            j = ne[j];//为下一次匹配做准备
        }
    }
}

KMP算法 — 模板2

next[i] = j的含义为：
含义1. 模板串第 i 个字母与主串对应字母不匹配时,模板串下一个要与主串对应字母匹配的位置为 j + 1
含义2. next[i] = j, 表示 t[1, j] = t[i - j + 1, i], 即以 i 结尾的最长公共前后缀的长度为 j

next函数

//next函数
void get_next(char t[], int ne[]){
    for(int i = 2, j = 0; i <= lent; i ++){
        while(j && t[i] != t[j + 1]) j = ne[j];
        if(t[i] == t[j + 1]) j ++;
        ne[i] = j;
    }
}

KMP算法 ---- 成功匹配一次后结束

//kmp算法, 匹配过程
int  index_kmp(char s[], char t[]){
    for(int i = 1, j = 0; i <= lens; i ++){
        while(j && s[i] != t[j + 1]) j = ne[j];
        if(s[i] == t[j + 1]) j ++;
    }
    if(j == lent) return i - lent + 1;
    return 0
}

KMP算法 ---- 成功匹配多次后结束

//kmp算法, 匹配过程
void kmp(char s[], char t[]){
    for(int i = 1, j = 0; i <= lens; i ++){
        while(j && s[i] != t[j + 1]) j = ne[j];
        if(s[i] == t[j + 1]) j ++;
        if(j == lent){//匹配成功
            cout << i - lent + 1<< ' ';
            j = ne[j];
        }
    }
}

经典试题

KMP字符串