kmp算法学习

前言：前段时间在写pta上面的代码题时遇到一个查找字符串字串的问题，一开始采取i，j循环遍历的方法暴力寻找，但是很可惜时间复杂度上出现问题，于是经过学习，初步尝试运用kmp算法来解决查找字符串字串中时间复杂度的问题。

对kmp的名称由来等就不展开描述了直接进入代码部分。

#include <stdio.h>
#include <string.h>
#include<stdlib.h>
void computeLPSArray(char* pat, int M, int* lps) {
    int len = 0,i=1;  // 当前最长前缀后缀长度
    lps[0] = 0;   // lps[0] 总是为 0
    while (i < M)
    {
        if (pat[i] == pat[len]) 
        {
            len++;
            lps[i] = len;
            i++;
        }
         else 
        {
            if (len != 0)   // 不匹配时，根据 lps 数组更新 len
            {
                len = lps[len - 1];
            }
            else 
            {
                lps[i] = 0;
                i++;
            }
        }
    }
}
void KMPSearch(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);
    int* lps = (int*)malloc(M * sizeof(int));  // 创建 lps 数组
    computeLPSArray(pat, M, lps);
    int i = 0; // txt 的索引
    int j = 0; // pat 的索引
    while (i < N)
    {
        if (pat[j] == txt[i])
        {
            i++;
            j++;
        }
        if (j == M)
        {
            printf("找到模式字符串 '%s' 的起始位置: %d\n", pat, i - j);
            j = lps[j - 1];
        } 
        else if(i < N && pat[j] != txt[i])
        {
            if (j != 0)   // 字符不匹配
            {
                j = lps[j - 1];
            } else
            {
                i++;
            }
        }
    }
}
int main(){
    char txt[] = "ABABDABACDABABCABAB";
    char pat[] = "ABABCABAB";
    KMPSearch(pat, txt);
    return 0;
}

个人理解，掌握kmp算法的关键就是掌握lps数组的构造（网上大部分也称next数组，就把lps换成next），lps数组也就是找字串中的最大公共前后缀，它可以帮助我们查找子串时优化“回溯”过程，因为用i，j单纯暴力循环每次都要回到最初会有很多浪费，利用lps数组的构造就可以优化这个过程。具体概念理解，以及构造思路还需要在网络上自己找视频理解。

接下来是pta里面的一道题，运用kmp算法解决。

7-11 删除字符串中的子串

分数 10

作者 白洪欢

单位 浙江大学

输入2个字符串S1和S2，要求删除字符串S1中出现的所有子串S2，即结果字符串中不能包含S2。

输入格式：

输入在2行中分别给出不超过80个字符长度的、以回车结束的2个非空字符串，对应S1和S2。

输出格式：

在一行中输出删除字符串S1中出现的所有子串S2后的结果字符串。

输入样例：

Tomcat is a male ccatat
cat

输出样例：

Tom is a male 

下面是通过代码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
// 计算LPS（最长前缀后缀）数组
void computeLPSArray(char* pat, int M, int* lps) {
    int len = 0; // 当前最长前缀长度
    lps[0] = 0; // lps[0] 总是为 0
    int i = 1; // 从 lps[1] 开始计算
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1]; // 根据 lps 更新 len
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}
// KMP搜索算法 - 查找并删除所有出现的子串
void KMPSearchAndDelete(char* txt, char* pat) {
    int M = strlen(pat);
    int N = strlen(txt);
    int* lps = (int*)malloc(M * sizeof(int));
    computeLPSArray(pat, M, lps);
    int i = 0; // 主串的索引
    int j = 0; // 模式串的索引
    while (i < N) {
        if (pat[j] == txt[i]) {
            i++;
            j++;
        }
        if (j == M) {
            // 找到一个匹配，删除子串
            memmove(&txt[i - j], &txt[i], N - i + 1); // 移动后面的字符
            N -= j; // 更新主串长度
            txt[N] = '\0'; // 确保以'\0'结束
            
            // 重置j为0，继续寻找进一步的匹配
            j = 0;
            i = 0; // 从头再继续检查
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) {
                j = lps[j - 1]; // 根据lps调整j
            } else {
                i++;
            }
        }
    }
    free(lps); // 释放内存
}
int main() {
    char s1[256]; // 增大数组大小以容纳更长的字符串
    char s2[81];
    fgets(s1, sizeof(s1), stdin);
    s1[strcspn(s1, "\n")] = 0; // 去掉换行符
    fgets(s2, sizeof(s2), stdin);
    s2[strcspn(s2, "\n")] = 0; // 去掉换行符
    // 持续删除子串直到找不到为止
    while (strstr(s1, s2) != NULL) {
        KMPSearchAndDelete(s1, s2); // 查找并删除子串
    }
    printf("%s\n", s1); // 输出结果
    return 0;
}