KMP算法(算法篇)

算法之KMP算法

KMP算法

概念

  • KMP算法是用于解决字符串匹配的问题的算法,也就是有一个文本串和一个模式串求解这个模式串是否在文本串中出现或者匹配
  • 相对于暴力求解,KMP算法使用了前缀表来进行匹配,充分利用了之前匹配的字符,减少了重新匹配全部模式串的时间。
  • 时间复杂度为O(m+n),其中n为文本串长度,m为模式串长度。

前缀表

例子:文本串:‘aabaabaaf’ ,模式串:‘aabaaf’

  • 前缀表也就是记录模式串的各子串最长相等前后缀长度(即字符串的前缀和后缀相等并且长度最长)的数组,而在KMP算法中是对模式串求解前缀表

  • 前缀字符串除了尾字符的子字符串都是前缀,模式串的前缀有:a、aa、aab、aaba、aabaa

  • 后缀字符串除了首字符的子字符串都是后缀,模式串的后缀有:f、af、aaf、baaf、abaaf

  • image

  • 根据上述的例子可以列出表格:

    image

  • 这样就对应着:aabaaf 010120,这个就为前缀表,而前缀表在KMP算法中被称为next数组或者prefix数组。next的意思就是指通过这个数组可以知晓下一步指针会跳到哪一步。

求解next数组

注:在遍历模式串的各个子串时,i为当前子串的后缀末尾索引j为当前字串的前缀末尾索引并且为数组索引小于等于i之前的子串的最长相等前后缀长度。子串是连续的字符形成的

  1. 初始化j初始化为0,因为模式串的第一个前缀子串为第一个字符,所以j索引指向0的位置,并且next[0]=0i初始化为1,用一个循环从索引i开始遍历模式串。(因为只有一个字符的子串没有相等前后缀)
  2. 前后缀不相同情况:为了充分利用之前已经匹配的字符,我们将对发生冲突的地方也就是前后缀末尾字符不匹配的时候,我们将对前缀末尾索引进行回溯到索引为next[j-1]的位置
  3. 前后缀相同情况当前后缀末尾字符相等的时候,就可以将j++,不仅将当前子串更新到下一个子串,还更新了当前子串的最长相等前后缀长度也就是next[i]=j

实现代码:

void getnext(int *next,const string& s,int size){
    //初始化
    int j=0;
    next[0]=0;
    for(int i=1;i<size;i++){
        //前后缀不相等情况
        while (j>0&&s[i]!=s[j]){
            j=next[j-1];    //回溯找到相等位置或者回到0
        }
        //前后缀相同情况
        if(s[i]==s[j]) j++;
        next[i]=j;
    }
}

KMP具体操作

  1. 求解next数组
  2. 然后利用求解next数组同等思路求解文本串出现模式串位置的索引,求解next数组是模式串前后缀末尾字符的比较,而文本串模式串匹配过程,是文本串与模式串的字符比较过程。
  3. j也就是文本串在索引大于等于i之前的子串与模式串最长匹配字符长度等于模式串的长度,就说明文本串出现了模式串,然后返回文本串中出现模式串的第一个字符的索引值(i-j+1)

KMP算法总体实现代码:

void getnext(int *next,const string& s,int size){
    //初始化
    int j=0;
    next[0]=0;
    for(int i=1;i<size;i++){
        //前后缀不相等情况
        while (j>0&&s[i]!=s[j]){
            j=next[j-1];    //回溯找到相等位置或者回到0
        }
        //前后缀相同情况
        if(s[i]==s[j]) j++;
        next[i]=j;
    }
}


int KMP(const string &text,const string &mode){
    int len=text.size();
    if(len==0) return 0;
    int size=mode.size();
    int j=0,next[size];
    getnext(next,mode,size);
    for(int i=0;i<len;i++){
        while (j>0&&text[i]!=mode[j]){
            j=next[j-1];
        }
        if(text[i]==mode[j]) j++;
        if(j==size) return (i-j+1);
    }
    return -1;    //未找到模式串
}

相关推荐

  1. KMP算法

    2024-07-22 01:18:04       70 阅读
  2. KMP算法

    2024-07-22 01:18:04       57 阅读
  3. <span style='color:red;'>kmp</span><span style='color:red;'>算法</span>

    kmp算法

    2024-07-22 01:18:04      49 阅读
  4. <span style='color:red;'>KMP</span><span style='color:red;'>算法</span>

    KMP算法

    2024-07-22 01:18:04      55 阅读
  5. KMP算法

    2024-07-22 01:18:04       45 阅读
  6. <span style='color:red;'>KMP</span><span style='color:red;'>算法</span>

    KMP算法

    2024-07-22 01:18:04      63 阅读
  7. KMP算法

    2024-07-22 01:18:04       37 阅读
  8. <span style='color:red;'>kmp</span><span style='color:red;'>算法</span>

    kmp算法

    2024-07-22 01:18:04      42 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-22 01:18:04       98 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-22 01:18:04       106 阅读
  3. 在Django里面运行非项目文件

    2024-07-22 01:18:04       87 阅读
  4. Python语言-面向对象

    2024-07-22 01:18:04       97 阅读

热门阅读

  1. 正态分布是什么

    2024-07-22 01:18:04       30 阅读
  2. deploy gitlab through docker

    2024-07-22 01:18:04       29 阅读
  3. 嵌入式软件技术能力

    2024-07-22 01:18:04       25 阅读
  4. Mad MAD Sum-Codeforces Round 960 (Div. 2)

    2024-07-22 01:18:04       28 阅读
  5. js | Core

    js | Core

    2024-07-22 01:18:04      23 阅读
  6. 堆、栈和队列(数据结构)

    2024-07-22 01:18:04       32 阅读
  7. 关于Spring Boot IOC&DC,看这一篇就够了

    2024-07-22 01:18:04       24 阅读
  8. 关于数据库索引

    2024-07-22 01:18:04       29 阅读