【数据结构】字符串匹配（kmp算法）

原理解析：

主串字符 a 和子串字符 b 匹配，主串和子串指针向后移动。 

主串字符 b 和子串字符 b 匹配，主串和子串指针向后移动。

主串字符 a 和 子串字符 c 不匹配，子串指针直接指向 next数组值指定编号字符。

主串字符 a 和 子串字符 a 匹配，主串和子串指针向后移动。

主串字符 b 和 子串字符 b 匹配，主串和子串指针向后移动。

主串字符 c 和 子串字符 c 匹配，主串和子串指针向后移动，这个时候主串和子串的指针都会指向空，判断 kmp 算法的成功标准为  子串指针移动次数等于子串长度。 

⚠为什么不能用主串指针移动的次数等于主串长度来判断 kmp 算法是否结束？

原因：子串走完而主串可能还没有与主串匹配成功。

next 数组怎么确定值？

公共前后缀：前面后面一样的前后缀。

前后缀：

eg：字符串 abacaba，其前缀有 a, ab, aba, abac, abacab，后缀有bacaba, acaba, caba, aba, ba, a

next 数组值 = 公共前后缀的长度 + 1

假设子串为 ABACCABABB，求这个子串的 next 数组

从第一个开始，遮住第一个到最后一个，看前面有没有公共前后缀。  

第一个元素字符前面没有内容，所以公共前后缀的长度为 0 ，第一个字符 next 数组值就为 0。

再从第二个开始，遮住第二个到最后一个，看前面有没有公共前后缀。 

只有字符 A ，没有公共前后缀，所以公共前后缀的长度为 0 ，第二个字符 next 数组值为 0 + 1 = 1。

再从第三个开始，遮住第三个到最后一个，看前面有没有公共前后缀。

字符 A 和 字符 B 没有公共前后缀，所以公共前后缀的长度为 0，第三个字符 next 数组值为 0 + 1 = 1。

再从第四个开始，遮住第四个到最后一个，看前面有没有公共前后缀。

字符 A 和 字符 A 有公共前缀，所以公共前后缀长度为 1，第四个字符 next 数组值为 1 + 1 = 2。

再从第五个开始，遮住第五个到最后一个，看前面有没有公共前后缀。

字符 A B A C 没有公共前后缀，所以公共前后缀长度为 0，第五个字符 next 数组值为 0 + 1 = 1。

再从第六个开始，遮住第六个到最后一个，看前面有没有公共前后缀。

字符 A B A C C 没有公共前后缀，所以公共前后缀长度为 0，第六个字符 next 数组值为 0 + 1 = 1。

再从第七个开始，遮住第七个到最后一个，看前面有没有公共前后缀。

字符 A B A C C A 有公共前后缀 A，所以公共前后缀的长度为 1，第七个字符 next 数组值为 1 + 1 = 2。

再从第八个开始，遮住第八个到最后一个，看前面有没有公共前后缀。

字符 A B A C C A B 公共前后缀 AB，所以公共前后缀长度为 2，第八个字符 next 数组值为 2 + 1 = 3。

再从第九个开始，遮住第九个到最后一个，看前面有没有公共前后缀。

字符 A B A C C A B A 公共前后缀 ABA，所以公共前后缀长度为 3，第九个字符 next 数组值为 3 + 1 = 4。

再从第十个开始（最后一个），遮住最后一个，看前面有没有公共前后缀。

字符 A B A C C A B A B 公共前后缀 AB，所以公共前后缀长度为 2，第十个字符 next 数组值为 2 + 1 = 3。

至此 next 数组求完。 

求 next数组的代码：

// 计算 next 数组
int* getNext(String* s) {
    int* next = (int*)malloc(sizeof(int) * s->size);
    int i = 0;
    int j = -1;
    next[i] = j;
    while (i < s->size - 1) {
        if (j == -1 || s->data[i] == s->data[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j]; // 子串回溯
        }
    }
    return next;
}

实践代码：

#include 
#include 
 
 
// KMP 算法 相对于 暴力怕破解的优化
 
// 主串指针没有回溯，快速达到匹配状态
 
// KMP 是一种高效的的模式匹配算法，牺牲了一定的空间去保存next数组
 
// 是当该字符不匹配后，值对应索引的字符要移动到跟主串不匹配的字符对齐
 
// 算法
// 公共前后缀：前面和后面一样的
// next 值 = 公共前后缀 + 1
 
// 减少主串指针的移动，快速找到能前后匹配的状态，从而加快匹配的进度
typedef struct String {
    char* data;
    int size;
}String;
 
// 初始化串
String* initString() {
    String* s = (String*)malloc(sizeof(String));
    s->data = NULL;
    s->size = 0;
    return s;
}
 
// 添加数据
void stringAssign(String* s, char* data) {
    if (s->data) {
        free(s->data);          
    }
    int len = 0;
    char* temp = data;
    while (*temp) {
        len++;
        temp++;
    }
 
    if (len == 0) {
        len = 0;
        s->data = NULL;
    }
    else {
        temp = data;
        s->size = len;
        s->data = (char*)malloc(sizeof(char) * (len + 1));
        for (int i = 0; i < len; i++, temp++) {
            s->data[i] = *temp;
        }
    }
}
 
// 输出字符串结构
void printString(String* s) {
    for (int i = 0; i < s->size; i++) {
        printf(i == 0 ? "%c" : "->%c", s->data[i]);
    }
    printf("\n");
}
 
// 计算 next 数组
int* getNext(String* s) {
    int* next = (int*)malloc(sizeof(int) * s->size);
    int i = 0;
    int j = -1;
    next[i] = j;
    while (i < s->size - 1) {
        if (j == -1 || s->data[i] == s->data[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
    return next;
}
 
// 输出 next 数组
void printNext(int* next, int len) {
    for (int i = 0; i < len; i++) {
        printf(i == 0 ? "%d" : "->%d", next[i] + 1);
    }
    printf("\n");
} 
 
// kmp 算法
void kmpMatch(String* master, String* sub, int* next) {
    int i = 0;
    int j = 0;
    while (i < master->size && j < sub->size) {
        if (j == -1 || master->data[i] == sub->data[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
    if (j == sub->size) {
        printf("匹配成功");
    }
    else {
        printf("未匹配成功");
    }   
}
 
int main() {
 
    String* s1 = initString();
    stringAssign(s1, "ABACCABABD");
 
    String* s2 = initString();
    stringAssign(s2, "CCAB");
 
    int* next = getNext(s2);
    printNext(next, s2->size);
 
    kmpMatch(s1, s2, next);
 
    return 0;
}

运行结果：

 kmp 是一种高效的模式匹配算法，他牺牲了一定的空间去保存 next 数组。