KMP算法(C语言实现)

简介: KMP算法(C语言实现)

思路

在经典的字符串匹配中,如果字符匹配失败i会返回到开始匹配时的后一个字符。这样会导致效率的下降。在KMP算法中,即使匹配失败i也不会动,只会J进行移动。

在匹配的过程中,字符相同时,就会进行下一对字符的匹配。当不相同时,如下面:

匹配失败,此时j需要回退,要回退到哪里呢?回退到下标为2的地方处。

原因如下:

i前面的字符都是匹配成功的,j前面的字符也是匹配成功的。常规情况下j要从头开始进行匹配,如果发现j前面的子串存在两个相同的真子串时(以下标0开始,以下标j-1结束),那么j就退回到真子串长度的位置处。如下面:

近一步解释,i前面的串和j前面的串相等,匹配时一定是从下标为0的位置匹配的,这也是找——以下标0开始,以下标j-1结束串——的原因,如果存在这两个串,则说明i前面一定存在以下标0

开始,以下标j-1结束串的子串。这样J退回的时候就省去了从头开始进行匹配。

这个串每个字符都有可能进行回退。回退的位置用一个数组进行储存,就形成了next数组

next数组

默认:0号位回退到-1处(在代码中处理,将不会造成数组越界问题)

1号位匹配失败退到0处。

现在主要的问题是如何实现next数组。

我们用K表示返回位置的下标,p是字符串,j表示下标。

假设next[j]=k成立(表达在j处匹配失败后返回到以k为下标处的位置)

那么p[0]····p[k-1]==p[x]····p[j-1]

(k处位置是从新匹配的地方,它前面的子串一定和j前面的子串相同)

从上面那个式子可以看出k-1-0=j-1-x即x=j-k;

式子就变成了p[0]····p[k-1]==p[j-k]····p[j-1] ——>next[j]=k成立的情况下

1️⃣当p[j]=p[k]

上面的式子可以变成p[0]····p[k-1] p[k]==p[j-k]····p[j-1] p[i]——>next[j+1]=k+1

2️⃣当p[j],p[k]不相等时,就会回退到k处,如果此时的k所对应k1,p[k1]=p[j]

那么next[j+1]=k1+1,否则继续回退,直到相等或者为-1处停止。

经过这样的过程,我们就得到了next数组

下面用图片给以进一步解释:下面的i是j,手残写错字母了。

next数组优化——>nextval数组

nextval数组的实现是根据next数组来实现的。

具体的求法:nextval数组的第一个元素为-1,第二个元素位0,以后j下标所对应的字符如果和以k对应的字符相等,那么nextval的元素nextval[k]中的元素。如果不相等,nextval的元素next里面的元素(即为k的值)

nextval数组

void my_nextval(int* nextval, char* p, int n)
{
  int k = -1, j = 0;
  nextval[0] = -1;
  while (j < n)
  {
    if (k == -1|| p[j] == p[k])
    {
      j++;
      k++;
      nextval[j] = k ;
      if (p[j] != p[k])
        nextval[j] = k;
      else
        nextval[j] = nextval[k];
    }
    else
    {
      k = nextval[k];
    }
  }
}

代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
void my_next(int* next,int n,const char* p)
{
  int j = 0,k=-1;
  next[0] = -1;
  while(j<n)
  {
    if (k == -1 || p[j] == p[k])
    {
      next[j + 1] = k + 1;
      j++;
      k++;
    }
    else
    {
      k = next[k];
    }
  }
}
int kmp(const char* str1, const char* str2)
{
  int i = 0, j = 0;
  int len = (int)strlen(str2);
  //next数组
  int* next = (int*)malloc(len * sizeof(int));
  assert(next);
  my_next(next,len-1,str2);
  while (str2[j])
  {
    if(j==-1||str1[i] == str2[j])
    //j为-1时该位置下的i不会匹配成功,进入下一次匹配
    {
      i++;
      j++;
    }
    else
    {
      j = next[j];//j进行回退
    }
    if (str1[i] == '\0')
    {
      free(next);
      next = NULL;
      return -1;
    }
  }
  free(next);
  next = NULL;
  return i;
}
int main()
{
  char arr[] = "abaabcdabcab";
  char brr[] = "ef";
  printf("%d\n",kmp(arr, brr));
  return 0;
}
相关文章
|
23天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
34 1
|
1月前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
57 4
|
22天前
|
存储 算法 程序员
C 语言递归算法:以简洁代码驾驭复杂逻辑
C语言递归算法简介:通过简洁的代码实现复杂的逻辑处理,递归函数自我调用解决分层问题,高效而优雅。适用于树形结构遍历、数学计算等领域。
|
23天前
|
存储 缓存 算法
C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力
本文探讨了C语言在实现高效算法方面的特点与优势,包括高效性、灵活性、可移植性和底层访问能力。文章还分析了数据结构的选择与优化、算法设计的优化策略、内存管理和代码优化技巧,并通过实际案例展示了C语言在排序和图遍历算法中的高效实现。
41 2
|
23天前
|
机器学习/深度学习 算法 数据挖掘
C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出
本文探讨了C语言在机器学习中的应用及其重要性。C语言以其高效性、灵活性和可移植性,适合开发高性能的机器学习算法,尤其在底层算法实现、嵌入式系统和高性能计算中表现突出。文章还介绍了C语言在知名机器学习库中的作用,以及与Python等语言结合使用的案例,展望了其未来发展的挑战与机遇。
39 1
|
23天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
存储 算法 数据管理
C语言算法复杂度
【10月更文挑战第20天】
C语言算法复杂度
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(上)(c语言实现)(附源码)
本文介绍了四种常见的排序算法:冒泡排序、选择排序、插入排序和希尔排序。通过具体的代码实现和测试数据,详细解释了每种算法的工作原理和性能特点。冒泡排序通过不断交换相邻元素来排序,选择排序通过选择最小元素进行交换,插入排序通过逐步插入元素到已排序部分,而希尔排序则是插入排序的改进版,通过预排序使数据更接近有序,从而提高效率。文章最后总结了这四种算法的空间和时间复杂度,以及它们的稳定性。
98 8
|
1月前
|
搜索推荐 算法 C语言
【排序算法】八大排序(下)(c语言实现)(附源码)
本文继续学习并实现了八大排序算法中的后四种:堆排序、快速排序、归并排序和计数排序。详细介绍了每种排序算法的原理、步骤和代码实现,并通过测试数据展示了它们的性能表现。堆排序利用堆的特性进行排序,快速排序通过递归和多种划分方法实现高效排序,归并排序通过分治法将问题分解后再合并,计数排序则通过统计每个元素的出现次数实现非比较排序。最后,文章还对比了这些排序算法在处理一百万个整形数据时的运行时间,帮助读者了解不同算法的优劣。
111 7
|
2月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法