20230804-字符串匹配算法（C语言实现）

前言

字符串匹配算法 又称模式匹配算法，该算法的目的是为了子串从主串中寻找是否有与其匹配的部分

其可分为BF暴力检索，RK 哈希检索，KMP BM 等等，本文仅介绍BF 算法和KMP 算法的视线，前者的时间复杂度是O(mn) ，后者的时间复杂度为O(m+n)，本文就是对这两者的核心思路进行总结分析，以加强记忆。

算法的思路如下：

代码实现如下：

#include<stdio.h>
#include<assert.h>
#include<string.h>
 
int BF(char* str, char* sub)//str代表主串，sub代表子串
{
  assert(str&&sub);//断言
  if (str == NULL || sub == NULL)//串为空值时直接返回-1
  {
    return -1;
  }
  int i = 0;//遍历主串
  int j = 0;//遍历子串
  int lenstr = strlen(str);//求出主串的长度
  int lensub = strlen(sub);//求出子串的长度
  while ((i < lenstr) && (j < lensub))//当子串遍历结束或主串遍历结束时，跳出循环
  {
    if (str[i] == sub[j])//匹配成功
    {
      i++;
      j++;
    }
    else//匹配失败
    {
      i = i - j + 1;
      j = 0;
    }
  }
  if (j >= lensub)//如果是因为子串遍历结束而跳出循环，说明匹配成功，返回下标
  {
    return i - j;
  }
  else//匹配失败，返回-1
    return -1;
}
int main()
{
  printf("%d\n", BF("ababcabcdabcde", "abcd"));//匹配成功，预期返回下标5
  printf("%d\n", BF("ababcabcdabcde", "abcds"));//匹配失败，返回-1
  printf("%d\n", BF("ababcabcdabcde", "ab"));//匹配成功，返回下标0
 
  return 0;
}

BF 算法缺点，有大量匹配无效，效率低

KMP 算法

1. 算法介绍

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特–莫里斯–普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。

2. 算法思路

next 数组的求解

例：有一个字符串ababcabc ，求其对应的next 数组

解 第一个字符对应的next 数组值为-1，第二个字符对应的next 数组值为0 ，从第三个字符开始，判断第一个字符和第n-1 个字符是否有匹配的

数学分析：

假设next[i]=k，可推出p[0]…p[k-1]=p[x]…p[i-1]，既k-1-0=i-1-x，得x=i-k

即p[0]…p[k-1]=p[i-k]…p[i-1]

若能证得p[i]==p[k]，则可求得next[i+1]=k+1。

若p[i]!=p[k]，next[i+1]=??

举个例子：

代码分析

void GetNext(char* sub, int* next, int lensub)/*sub代表子串；next是外部开辟的动态内存数组；lensub是子串长度*/
{
  next[0] = -1;
  next[1] = 0;
  int i = 2;//当前i下标
  int k = 0;//前一项的k
 
  while(i < lensub)
  {
    if (k == -1 || sub[i - 1] == sub[k])//k回退到-1或前一项sub[i-1]==sub[k]
    {
      next[i] = k + 1;
      i++;
      k++;
    }
    else
    {
      k = next[k];//if条件不满足时则需将k回退到-1下标
    }
  }
}

附加知识：next 数组的优化

同样以例子来讲

图中所示，当i=5时匹配失败，若按照nextr 数组回退的话，到i=4时，依旧是a，匹配失败还得回退，每次回退都是相同的字符，这些回退无疑是无效的。而nextval数组就是对这一现象的优化。

3.整体代码的实现

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void GetNext(char* sub, int* next, int lensub)/*sub代表子串；next是外部开辟的动态内存数组；lensub是子串长度*/
{
  next[0] = -1;
  next[1] = 0;
  int i = 2;//当前i下标
  int k = 0;//前一项的k
 
  while(i < lensub)
  {
    if (k == -1 || sub[i - 1] == sub[k])//k回退到-1或前一项sub[i-1]==sub[k]
    {
      next[i] = k + 1;
      i++;
      k++;
    }
    else
    {
      k = next[k];//if条件不满足时则需将k回退到-1下标
    }
  }
}
 
int KMP(char* str, char* sub, int pos)/*str:代表主串；sub:代表子串；pos:代表从主串的pos位置开始找*/
{
  assert(str&&sub);//断言
  if (str == NULL || sub == NULL)//字符串为空直接返回-1
    return -1;
  int lenstr = strlen(str);//求主串长度
  int lensub = strlen(sub);//求子串长度
  if (pos < 0 || pos >= lenstr)//pos位置不合法直接返回-1
    return -1;
 
  int *next = (int*)malloc(sizeof(int)*lensub);//开辟动态内存给next数组存放数据
  assert(next);
 
  GetNext(sub, next,lensub);//求出next数组
 
  int i = pos;//遍历主串
  int j = 0;//遍历子串
 
  while (i < lenstr&&j < lensub)
  {
    if (j == -1 || str[i] == sub[j])
    {
      i++;
      j++;
    }
    else
    {
      j = next[j];
    }
  }
  free(next);
  next = NULL;
  if (j >= lensub)
  {
    return i - j;
  }
  return -1;
}
 
int main()
{
  printf("%d\n", KMP("ababcabcdabcde", "abcd", 0));//预期返回5
  printf("%d\n", KMP("ababcabcdabcde", "abcdf", 0));//预期返回-1
  printf("%d\n", KMP("ababcabcdabcde", "ab", 0));//预期返回0
  return 0;
}

总结

以上就是今天要讲的内容，本文介绍了关于字符串匹配的BF算法和KMP算法，通过比特大博哥的视频学习，对算法思路与实现代码进行理解和分析，简单学习记录。欢迎大家探讨指正！

打赏