說(shuō)明
kmp的一些概述不做解釋了, 請(qǐng)參考: kmp算法 (百度百科)
參考了 阮一峰的: 字符串匹配的KMP算法
使用 C 語(yǔ)言實(shí)現(xiàn)的算法

部分匹配表
指在一串字符串中, 前綴與后綴中所共有的字符
前綴: 不包含字符串最后一個(gè)字符
后綴: 不包含字符串第一個(gè)字符

例如字符串 (AHABAD)
由此得出他們的部分匹配表為

A -> 0
前后都沒(méi)有所有共有字符數(shù)所以為 0

AH -> 0
前綴: A
后綴: H
它們沒(méi)有功能字符所有為 0

AHA -> 1
前綴: A, AH
后綴: A, HA
它們有共有的字符 共有數(shù)為 1

AHAB -> 0
前綴: A, AH, AHA
后綴: B, AB, HAB
它們沒(méi)有共有字符所有為 0

AHABA -> 1
前綴: A, AH, AHA, AHAB
后綴: A, BA, ABA, HABA
它們有共有字符 共有數(shù)為 1

由此得出 AHABAD 的前綴表為

部分匹配表算法實(shí)現(xiàn)過(guò)程 C 語(yǔ)言

int* prefix(char* s){
    /*
        接收一個(gè)字符串,
        返回一個(gè)部分匹配表  
    */

    int len = strlen(s),
        i = 0,
        j = -1, 

        *p = malloc(sizeof(int) * len);

    p[0] = -1;

    while(i < len - 1){
        if(j == -1 || s[i] == s[j]){
            p[++i] = ++j;
            continue;
        }
        j = p[j];
    }

    return p;
}

變量 i && j && p 的作用
在這里 p 可以看作是一次回溯,
應(yīng)為每當(dāng) if 條件不滿(mǎn)足時(shí) 則進(jìn)行一次回溯
那么此時(shí) j 的位置就需要重置到 p[j]

部分匹配表生成過(guò)程 以字符串 AHABAD 為例

kmp

//kmp匹配算法
int kmpSearch(char *t, char *s){
    int t_len = strlen(t), 
        s_len = strlen(s);

    int *p = prefix(s), 
        m = 0, //代表母串匹配到的位置
        j = 0; // 代表字符匹配到的位置

    while(t_len > m && s_len > j){
        //j == -1 那么代表不和任何匹配直接向后移動(dòng)以為
        if(j == -1 ||  t[m] == s[j]){
            m++;
            j++;
            continue;
        }
        //當(dāng)不相等時(shí), 就去查詢(xún)部分匹配表
        j = p[j];
    }

    if (j == s_len)
        //返回匹配到的索引位置
        return m - j;
    return -1;
}

完整代碼
所需頭文件:
string.h stdlib.h

//部分匹配表算法
int* prefix(char* s){
    //prefix table
    int len = strlen(s),
        i = 0,
        j = -1, 
        *p = malloc(sizeof(int) * len);
    p[0] = -1;

    while(i < len - 1){
        if(j == -1 || s[i] == s[j]){
            p[++i] = ++j;
            continue;
        }
        j = p[j];   
    }

    return p;
}

//kmp
int kmpSearch(char *t, char *s){
    int t_len = strlen(t), 
        s_len = strlen(s);

    int *p = prefix(s), 
        m = 0,
        j = 0;

    while(t_len > m && s_len > j){
        if(j == -1 ||  t[m] == s[j]){
            m++;
            j++;
            continue;
        }
        j = p[j];
    }

    if (j == s_len)
        return m - j;
    return -1;

}