参考阮一峰http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

参考博客https://www.cnblogs.com/wangguchangqing/archive/2012/09/09/2677701.html

朴素的模式匹配算法

/*
        朴素的模式匹配算法
        功能：字符串的模式匹配
        参数：
            s：目标串
            p：模式串
            pos：开发匹配的位置
        返回值：
           匹配成功，返回模式串在目标串的其实位置
           匹配不成功，返回-1
  */
int match(const char *s, const char *p, int pos) {
    int i = pos;
    int j = 0;
    while (s[i] != '\0' && p[j] != '\0') {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            i = i - j + 1;
            j = 0;
        }
    }

    if (p[j] == '\0')
        return i - j;
    else
        return -1;
}

KMP算法

/*
    KMP进行模式匹配的辅助函数
    模式串和主串匹配不成功时，下次和主串进行匹配的模式串的位置
*/
void continue_prefix_function(const char *p, int *next) {
    int j;
    int k;
    next[0] = -1;
    j = 0;
    k = -1;

    while (j < strlen(p) - 1) {
        if (k == -1 || p[k] == p[j]) {
            j++;
            k++;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}


/*
    运用KMP算法的字符串模式匹配
    在主串和模式串匹配不成功时，不对主串指针进行回溯，
    例如用next[j],来指定下一次和主串进行匹配的模式串的位置
*/
int match_kmp(const char *s, const char *p, int pos) {
    int next[11];
    int i = pos;
    int j = 0;
    continue_prefix_function(p, next);
    while (s[i] != '\0' && p[j] != '\0') {
        if (s[i] == p[j]) {
            i++;
            j++;
        } else {
            if (next[j] == -1) {
                i++;
                j = 0;
            } else {
                j = next[j];
            }
        }
    }
    if (p[j] == '\0')
        return i - j;
    else
        return -1;
}


int main() {
    cout << match_kmp("BBC ABCDAB ABCDABCDABDE", "ABCDABD", 0);
}