【数据结构】模式匹配之KMP算法与Bug日志—C/C++实现

​🌈个人主页：Sarapines Programmer
🔥 系列专栏：《数据结构奇遇记》
🔖墨香寄清辞：墨痕寄壮志，星辰梦未满。 通幽径心凝意，剑指苍穹势如山。

目录

🌞1. 模式匹配的基本概念

🌞2. 模式匹配的解决办法

🎈2.1 暴力匹配(BF)算法

🎈2.2 KMP算法

🤖2.3 BUG记录_KMP算法

🌞1. 模式匹配的基本概念

1.1 模式匹配是在字符串 s （称为目标串）中寻找字符串 t （称为模式串）的过程。

1. 目标串： 这是要进行搜索的字符串，包含了我们需要查找模式的信息。

2. 模式串： 这是要在文本串中寻找的具体字符串或子字符串。

示例：目标串s="aaaaab",模式串t="aaab".

1.2 常见的模式匹配算法：

• 暴力匹配(BF)算法： 从文本串的第一个字符开始，逐一与模式串比较，如果不匹配，则移动到下一个位置。

• KMP算法： 通过预处理模式串，构建一个部分匹配表next[]，利用已匹配的信息来避免不必要的比较，提高匹配效率。

  ---

  🌞2. 模式匹配的解决办法

  🎈2.1 暴力匹配(BF)算法

  从头开始遍历寻找，若不匹配则主串的指针i返回，从下一个地址开始（i-j+1）

  简单示例：目标串s="aaaaab",模式串t="aaab".若成功返回匹配成功的位置，否则返回0.

  #include 
  #include 
  using namespace std;
  int BF(string s,string t){
      int i=0,j=0;
      while(i