正文 

当前位置： 首页 > 技术 > java教程

kmp算法(代码片段)

authetic authetic     2023-02-04     686

关键词：

概述

KMP(Knuth-Morris-Pratt)算法是一种用来解决字符串匹配问题的算法，时间复杂度为O(n+m)，主要思想是当模式串与主串发生失配时，不必从头开始匹配，而是滑动到已经匹配的部分

next数组

在KMP算法中，next数组用来存储一段子串最大相等前后缀的长度加1，例如长度为i+1的字符串，它的最大相等前后缀分别为0~k和i-k~i，则next[i]=k，这里k小于i。
问题在于如何去求next数组，遍历的话KMP算法就没什么意义了，但仔细观察就可以发现next[i]的值可以由已求出的next数组的值推导出

求next[i+1]只需考虑两种情况

  1. s[i+1] == next[i] + 1，则next[i+1] = next[i] + 1
  2. s[i+1] != next[i] = 1

对于第二种情况，我们需要一个变量j，我们令j=next[next[i]]，如果s[i+1] == s[j+1]，则next[i+1]=j+1。我认为整个KMP的精髓就在这里，这也是最难理解的一步。其实再看一下next数组的意义就知道了，这里s[0~j]肯定等于s[i-j~i]，这里的一部分就是s[next[i]]所匹配出来的最大前后缀，如图所示

技术分享图片

这样我们就可以轻松的求出next数组了

void getnext(char s[], int len) 
    int j = -1, next[0] = -1;
    for(int i = 0; i < n; i ++ ) 
        while (j != -1 && s[i] != s[j+1]) 
            j = next[j];
        
        if (s[i] == s[j+1]) 
            j++;
        
        next[i] = j;

KMP算法的实现

命名变量i和j，i表示主串预匹配的下标，j表示模式串已匹配的下标，那么每次匹配过程无非有两种情况

  1. text[i] == pattern[j+1]
  2. text[i] != pattern[j+1]

对于第二种情况，我们不断地让j=next[j]，直到text[i] == pattern[j+1]或者j等于-1

算法实现

bool KMP(char text[], char pattern[]) 
    int n = strlen(text), m = strlen(pattern);
    int next[m];
    getnext(pattern, m);
    int j = -1;
    for (int i = 0; i < n; i ++ ) 
        while (j != -1 && text[i] != pattern[j+1]) 
            j = next[j];
        
        if (text[i] == pattern[j+1]) 
            j++;
        
        if (j == m-1) 
            return true;
        
    
    return false;

算法优化

在while循环里每次回退找到j的过程可以更快一些，通过优化求解next数组的部分，因为如何已知s[j+1]==s[i+1]，j肯定还要回退，我们直接让next数组存储每次适配时需要回到的那个j

void getnextval(char s[], int len) 
    int j = -1, nextval[0] = -1;
    for (int i = 0; i < len; i ++ ) 
        while (j !=1 && s[j+1] != s[i]) 
            j = nextval[i];
        
        if (s[j+1] == s[i]) 
            j++;
        
        if (j == -1 || s[j+1] != s[i+1]) 
            nextval[i] = j;
         else 
            nextval[i] = nextval[j];

kmp算法(代码片段)

KMP算法KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达... 查看详情

kmp算法(代码片段)

KMP算法给定文本串A、模式串B，求模式串B在文本串A中出现的次数。设文本串A的长度为n，模式串B的长度为m暴力：二重循环+回溯复杂度O(n*m)KMP:将复杂度优化到O(n+m)本篇文章是我初学KMP算法所写，如果有错误欢迎指出另外本文的KM... 查看详情

kmp算法(代码片段)

　　关于KMP入门，可以参考：KMP入门。　　另外附上我自己的KMP代码：　　#include<cstring>#include<iostream>#include<cstdio>usingnamespacestd;constintMAXL=1000001;chars1[MAXL],s2[MAXL];intla,lb;intnext[MAXL];voidclcN 查看详情

kmp算法实现(代码片段)

KMP算法实现packagecom.wwz.kmp;importjava.util.Arrays;publicclassKmpDeom publicstaticvoidmain(String[]args) //TODO自动生成的方法存根 Stringstr1="aabcdabd"; Stringstr2="abcdabd"; int[]a& 查看详情

kmp算法(代码片段)

1.KMP算法介绍在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用... 查看详情

kmp算法(代码片段)

1.KMP算法介绍在计算机科学中，Knuth-Morris-Pratt字符串查找算法（简称为KMP算法）可在一个字符串S内查找一个词W的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用... 查看详情

kmp算法(代码片段)

字符串KMP算法前言KMP，作为字符串的入门算法，还是比较有难度的。起码当初我尝试理解KMP的时候，就花了整整一个上午去翻阅各种博客。虽然每一篇博客在理解之后再去看会发现说得都挺有道理，但是在云里雾里的时候，并不... 查看详情

kmp算法详解(代码片段)

文章目录前言例题引入简单算法BF经典算法KMPkmp理解难点1kmp理解难点2kmp最难理解点3kmp代码前言对于kmp的鼎鼎大名,不只是博主自己,想必还有更多小伙子们听说过,也相信都去了解过,博主亦是这样,但是真正去理解这个过程,确是异... 查看详情

kmp算法(代码片段)

KMP算法避免从头匹配：最长相同前缀后缀next[]：实现最长相同前缀后缀的思路递推分析：最长相同前缀后缀，从哪里来实现KMP算法 避免从头匹配：最长相同前缀后缀KMP第一个线性的字符串匹配算法。算法的优... 查看详情

javajava实现的kmp算法(代码片段)

查看详情

扩展kmp算法学习扩展kmp算法学习(粗)(代码片段)

参考：扩展KMP算法问题定义：给定两个字符串S和T（长度分别为n和m），下标从0开始，定义extend[i]等于S[i]...S[n-1]与T的最长相同前缀的长度，求出所有的extend[i]。如下表所示：i0123456SaaaaabbTaaaaacextend[i]5432100#include<iostream>#include... 查看详情

kmp算法的两种实现(代码片段)

前言朴素子字符串查找算法KMP算法的基本思想基于DFA的KMP实现基于PMT的KMP实现历史渊源&DFA&PMT结语参考链接前言KMP算法在LeetCode刷题的过程中看见过好几次，这几天终于去学习了一下，然后，我就发现，Google出来的KMP和我书... 查看详情

kmp算法(代码片段)

基本介绍KMP算法是一种用于字符串匹配的算法，网上关于kmp的介绍很多，也十分复杂，（其实我也没怎么搞懂）。首先我们还是考虑朴素的匹配，暴力枚举匹配起点，遇到不匹配的点，就直接退出，进行下一个起始点开始的一轮... 查看详情

kmp算法(代码片段)

什么是KMP？KMP算法要解决的问题就是在字符串（也叫主串）中的模式（pattern）定位问题。说简单点就是我们平时常说的关键字搜索。 1publicclassKMP23publicstaticintKMP(Stringstr1,Stringstr2)4intlen1=str1.length();//str1的长度主串5intlen2=str2.len... 查看详情

kmp算法(代码片段)

http://acm.zjnu.edu.cn/DataStruct/showproblem?problem_id=1005题解：kmp模板题。如何理解kmp？ 背下来就好了#define_CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include<string>#include&l 查看详情

bf与kmp算法的初步认知(代码片段)

算法介绍BF（暴力匹配算法）代码实现KMP（模式匹配算法）举例分析（逻辑分析）next数组代码实现next组KMP算法的实现时间复杂度分析总结算法介绍BF（暴力匹配算法）BF算法，即暴力(BruteForce)算... 查看详情

kmp算法(代码片段)

数据结构_串对于串,今天就总结了一个算法,关于字符串的模式匹配问题(重点在于kmp算法).普通的模式匹配算法,当匹配不成功时需要将主串的下标恢复到之前匹配的下一个字符,子串下标置为串首;而kmp算法则不需要重置主串的下标... 查看详情

kmp算法(代码片段)

目录KMP算法基本思想计算next数组前缀和后缀公共部分的最大长度next数组匹配字符串KMP算法基本思想算法由两部分组成计算ptr每一位及之前的字符串中，前缀和后缀公共部分的最大长度的next数组匹配ptr和str，当ptr失配时，利用nex... 查看详情