关键词：

Kmp算法浅谈

一.Kmp算法思想

在主串和模式串进行匹配时，利用next数组不改变主串的匹配指针而是改变模式串的匹配指针，减少大量的重复匹配时间。在Kmp算法中，next数组的构建是整个Kmp算法的核心所在。

二.Kmp核心之next数组的构建

（1）前缀，后缀的定义

（2）最长公共前后缀定义

（3）next数组的含义

next数组代表各个长度子串(这些字串的起始位置都为0)的最长公共前后缀长度，为了方便代码的编写next[0]定为-1，表示前0个字符根本不存在前后缀这一说法。其他的例如next[1]表示前一个字符的 最长公共前后缀 ，很明显根据前后缀的定义，next[1]=0;next[1]和next[0]在本博客说明的next数组构成中是唯一和确定的。

（4）最长公共前后缀定义及与next的联系

（5）对于一个模式串next数组到底能表示什么

首先根据上面的说法next数组表示了模式串长度为i的前缀的最长公共前后缀的的长度，所以说next可以来表示长度。这个时候我们在深究一下它表示的是谁的长度？它表示的是最长公共前后缀的!!!!,也就是说它可以表示模式串中第next[i]个元素的下标!!!,不懂的话看图就明白了

（6）如何利用next数组的性质避免重复匹配呢

三.如何用代码的形式得到next数组

首先上个代码

void Getnext(int next[],char *MyString)

   int j=0,k=-1;
   next[0]=-1;//规定，方便后面k的计算
   while(j<strlen(MyString)-1)//j不能超过整个串的长度
   
      //j为当前字符,k为j前面那些字符的最长公共前后缀的下一个字符
      if(k == -1 || MyString[j] == MyString[k])next[++j] = ++k;
      //模式串的第一个字符就要比较的字符不一样,那我就要将模式串的下一个字符和我要比较的字符比较，且现在k还是为-1的，所以++j,++k
      else k = next[k];
   

三.Kmp算法代码

得到了next后一切就简单了，无非就是设定两个“指针”分别指向主串和模式串，当出现不匹配时模式串的指针根据next数组移动就好了，直接上代码

int Kmp(char *T,int numt,char *P,int nump,int *next)//T为主串，P为模式串 

    int i=0,j=0;//i为主串的指针，j为模式串的指针
    while(i<=numt-nump)
    
        while((T[i]==P[j]&&i<numt)||j==-1) ++i,++j;//j==-1
//模式串第一个就和主串中要匹配的字符不匹配，主串字符后移一位，模式串的指针也从-1恢复到零
        if(j==nump)//找到匹配串
        return i-nump;//返回在主串中的起始位置
        j=next[j];
    
    return -1;//表示无法找到 

四.整个程序完整代码

#include <stdio.h>
#include <string.h>
void Getnext(int next[],char *MyString);
int Kmp(char *T,int numt,char *P,int nump,int *next); 
const int SIZE=256;
int main()

    char *T=new char[SIZE];
    char *P=new char [SIZE];
    int *next=new int [SIZE];
    scanf("%s",T);
    scanf("%s",P);
    Getnext(next,P);
    for(int i=0;i<strlen(P);i++) printf("%d,",next[i]); 
    printf("
%d",Kmp(T,strlen(T),P,strlen(P),next));
    return 0;
 
void Getnext(int next[],char *MyString)

   int j=0,k=-1;
   next[0]=-1;
   while(j<strlen(MyString)-1)
   
      if(k == -1 || MyString[j] == MyString[k])next[++j] = ++k;
      else k = next[k];
   

int Kmp(char *T,int numt,char *P,int nump,int *next)//T为主串，P为模式串 

    int i=0,j=0;//i为主串的指针，j为模式串的指针
    while(i<=numt-nump)
    
        while((T[i]==P[j]&&i<numt)||j==-1) ++i,++j;
        if(j==nump)//找到匹配串
        return i-nump;//返回在主串中的起始位置
        j=next[j];
    
    return -1;//表示无法找到 

kmp算法浅谈(代码片段)

Kmp算法浅谈一.Kmp算法思想在主串和模式串进行匹配时，利用next数组不改变主串的匹配指针而是改变模式串的匹配指针，减少大量的重复匹配时间。在Kmp算法中，next数组的构建是整个Kmp算法的核心所在。二.Kmp核心之next数组的构... 查看详情

浅谈算法——kmp(代码片段)

KMP是啥？KMP当然是KMPlayer的简称啦KMP算法是用来解决字符串匹配的一种算法，由D.E.Knuth、J.H.Morris和V.R.Pratt同时发现，然后它可以用来干啥呢？我们上个例题：给定两个字符串(S,T)，问(T)在(S)中出现了多少次，出现的起始位置不同... 查看详情

浅谈kmp(代码片段)

...串在第一个字符串中的位置暴力匹配的话大概就是下文的算法1for(inti=0;i<str1len;i++)2intflag=1;3for(intj=0;j<str2len;j++)4if(str1[i+j]!=str2[j]5flag=0;6break;789if(flag)printf("%d",i);1011//strl1len指lengthofstring1也就是字符串1的长度。12//str1指第一个字... 查看详情

浅谈kmp(代码片段)

....H.Morris）和Pratt(V.R.Pratt）三人设计的线性时间字符串匹配算法。这个算法不用计算变迁函数δ，匹配时间为Θ（n），只用到辅助函数π[1，m]，它是在Θ（m）时间内，根据模式预先计算出来的。数组π使得我们可以按需要，“现场... 查看详情

kmp算法(代码片段)

KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情

kmp算法(代码片段)

KMP算法写OJ时做到字符串匹配问题，用暴力算法结果超出时间限制了，其实早就知道这种问题可以用kmp算法解决，但是我一直懒得学，于是借助这个OJ来记录一下学习kmp算法的一些个人理解文章目录KMP算法字符串匹... 查看详情

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和我书... 查看详情