KMP(Knuth-Morris-Pratt)算法详解及C++代码实现

2024-06-02 09:36

本文主要是介绍KMP(Knuth-Morris-Pratt)算法详解及C++代码实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

在计算机科学中,字符串匹配是一个基础且重要的任务。给定一个主字符串(也称为文本)和一个模式字符串(也称为词),字符串匹配算法的任务是在主字符串中查找与模式字符串相同的子串,并返回其位置。Knuth-Morris-Pratt(KMP)算法是一种高效的字符串匹配算法,由D.E. Knuth、J.H. Morris和V.R. Pratt联合提出。该算法通过减少不必要的字符比较次数,从而提高了字符串匹配的效率。

一、KMP算法的基本思想

KMP算法的基本思想利用已经部分匹配这个有效信息,保持主字符串(记为S)的指针不回溯,通过修改模式字符串(记为P)的指针位置,让模式字符串尽量地“滑动”,使得每次回溯都能比暴力匹配算法减少更多的比较次数。为了达到这个目的,KMP算法需要预处理模式字符串,得到一个“部分匹配表”(也称为“失败函数表”或“跳转表”),该表记录了当模式字符串中的某个字符与主字符串的当前字符不匹配时,模式字符串应该向前移动多少位。

二、KMP算法的实现步骤

  1. 预处理部分匹配表

    • 初始化一个数组next,用于存储部分匹配表。
    • j = 0k = -1next[0] = -1
    • j < 模式字符串长度时,进行循环:
      • 如果k == -1模式字符串[j] == 模式字符串[k],则j++k++next[j] = k
      • 否则,k = next[k]
    • 预处理完成后,next数组就存储了模式字符串的部分匹配表。
  2. 字符串匹配

    • 初始化两个指针ij,分别指向主字符串和模式字符串的起始位置。
    • i < 主字符串长度j < 模式字符串长度时,进行循环:
      • 如果主字符串[i] == 模式字符串[j],则i++j++
      • 如果j已经等于模式字符串的长度,说明找到了一个匹配,输出匹配位置i - j,并将j重置为0,继续下一轮匹配。
      • 如果主字符串[i] != 模式字符串[j],则根据next[j]的值更新j,即j = next[j]
    • 如果循环结束且没有找到匹配,则返回未找到匹配的标识。

三、KMP算法的时间复杂度

KMP算法的时间复杂度主要取决于预处理部分匹配表的时间和实际的匹配过程。预处理部分匹配表的时间复杂度为O(m),其中m为模式字符串的长度。实际的匹配过程的时间复杂度为O(n+m),其中n为主字符串的长度。因此,KMP算法的总时间复杂度为O(n+m)。

四、KMP算法的C++代码实现

#include <iostream>
#include <vector>
#include <string>using namespace std;// 获取部分匹配表
vector<int> getNext(const string& pattern) {int m = pattern.length();vector<int> next(m, 0);int j = 0, k = -1;next[0] = -1;while (j < m - 1) {if (k == -1 || pattern[j] == pattern[k]) {++j;++k;next[j] = k;} else {k = next[k];}}return next;
}// KMP算法
int kmpSearch(const string& str, const string& pattern) {int n = str.length();int m = pattern.length();vector<int> next = getNext(pattern);int i = 0, j = 0;while (i < n && j < m) {if (j == -1 || str[i] == pattern[j]) {++i;++j;} else {j = next[j];}}if (j == m) {return i - j; // 匹配成功,返回匹配开始的位置} else {return -1; // 匹配失败,返回-1}  
}  // 主函数  
int main() {  string str = "ABABDABACDABABCABAB";  string pattern = "ABABCABAB";  int pos = kmpSearch(str, pattern);  if (pos != -1) {  cout << "Pattern found at position: " << pos << endl;  } else {  cout << "Pattern not found." << endl;  }  return 0;  
}

五、代码详解

1、getNext函数:该函数用于获取模式字符串的部分匹配表。在循环中,我们比较当前字符pattern[j]和pattern[k],如果它们相等,则继续向后移动两个指针;如果不相等,则将k回溯到next[k]的值,再次进行比较。需要注意的是,当pattern[j]和pattern[k]相等时,我们需要检查pattern[j+1]和pattern[k+1]是否也相等,以确定next[j+1]的值。
2、kmpSearch函数:该函数实现了KMP算法的核心逻辑。我们使用两个指针i和j分别指向主字符串和模式字符串的当前位置。在循环中,我们比较str[i]和pattern[j],如果它们相等,则继续向后移动两个指针;如果不相等,则将j回溯到next[j]的值,再次进行比较。当j等于模式字符串的长度时,说明找到了一个匹配,返回匹配开始的位置;如果循环结束且没有找到匹配,则返回-1。
3、main函数:在主函数中,我们定义了一个主字符串str和一个模式字符串pattern,并调用kmpSearch函数进行匹配。根据返回的结果,我们输出相应的信息。

六、总结

KMP算法是一种高效的字符串匹配算法,它通过预处理模式字符串的部分匹配表来减少不必要的字符比较次数。在C++中实现KMP算法时,需要注意部分匹配表的获取和字符串匹配的逻辑。通过上面的代码示例和详解,我们可以更好地理解KMP算法的实现原理和应用方法。

这篇关于KMP(Knuth-Morris-Pratt)算法详解及C++代码实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1023601

相关文章

Python位移操作和位运算的实现示例

《Python位移操作和位运算的实现示例》本文主要介绍了Python位移操作和位运算的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 位移操作1.1 左移操作 (<<)1.2 右移操作 (>>)注意事项:2. 位运算2.1

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出(如HTML、XML、邮件内容等),本文... 目录什么是 FreeMarker 模板?在 Spring Boot 中实现 FreeMarker 模板1. 环

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

SpringMVC 通过ajax 前后端数据交互的实现方法

《SpringMVC通过ajax前后端数据交互的实现方法》:本文主要介绍SpringMVC通过ajax前后端数据交互的实现方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价... 在前端的开发过程中,经常在html页面通过AJAX进行前后端数据的交互,SpringMVC的controll

Java Stream流使用案例深入详解

《JavaStream流使用案例深入详解》:本文主要介绍JavaStream流使用案例详解,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录前言1. Lambda1.1 语法1.2 没参数只有一条语句或者多条语句1.3 一个参数只有一条语句或者多

Spring Security自定义身份认证的实现方法

《SpringSecurity自定义身份认证的实现方法》:本文主要介绍SpringSecurity自定义身份认证的实现方法,下面对SpringSecurity的这三种自定义身份认证进行详细讲解,... 目录1.内存身份认证(1)创建配置类(2)验证内存身份认证2.JDBC身份认证(1)数据准备 (2)配置依

利用python实现对excel文件进行加密

《利用python实现对excel文件进行加密》由于文件内容的私密性,需要对Excel文件进行加密,保护文件以免给第三方看到,本文将以Python语言为例,和大家讲讲如何对Excel文件进行加密,感兴... 目录前言方法一:使用pywin32库(仅限Windows)方法二:使用msoffcrypto-too

C#使用StackExchange.Redis实现分布式锁的两种方式介绍

《C#使用StackExchange.Redis实现分布式锁的两种方式介绍》分布式锁在集群的架构中发挥着重要的作用,:本文主要介绍C#使用StackExchange.Redis实现分布式锁的... 目录自定义分布式锁获取锁释放锁自动续期StackExchange.Redis分布式锁获取锁释放锁自动续期分布式

springboot使用Scheduling实现动态增删启停定时任务教程

《springboot使用Scheduling实现动态增删启停定时任务教程》:本文主要介绍springboot使用Scheduling实现动态增删启停定时任务教程,具有很好的参考价值,希望对大家有... 目录1、配置定时任务需要的线程池2、创建ScheduledFuture的包装类3、注册定时任务,增加、删

SpringBoot整合mybatisPlus实现批量插入并获取ID详解

《SpringBoot整合mybatisPlus实现批量插入并获取ID详解》这篇文章主要为大家详细介绍了SpringBoot如何整合mybatisPlus实现批量插入并获取ID,文中的示例代码讲解详细... 目录【1】saveBATch(一万条数据总耗时:2478ms)【2】集合方式foreach(一万条数