KMP算法

简介: 问题描述输入:一个文本串S,和一个模式串P输出:若干行,每行包含一个整数,表示s2在s1中出现的位置在一个母字符串S(文本串)中查找一个子字符串P(模式串)有很多方法。

问题描述

输入:一个文本串S,和一个模式串P
输出:若干行,每行包含一个整数,表示s2在s1中出现的位置

在一个母字符串S(文本串)中查找一个子字符串P(模式串)有很多方法。Knuth-Morris-Pratt 字符串查找算法(简称“KMP”)是一种最常见的改进算法,由Donald Knuth、Vaughan Pratt、James H. Morris三人于1977年联合发表,故取这3人的姓氏命名此算法。

这个算法针对的是子串有对称属性,如果有对称属性,那么就需要向前查找是否有可以再次匹配的内容。

注意:这里的对称性,不是中心对称,而是中心字符块对称,比如不是abccba,而是abcabc这种对称。


KMP

一般最粗暴的方法,就是匹配失败后,一个字符一个字符往后挪来进行比较,比如:


img_dfa7f924bee9d5f0acf1512ec4a011f7.png
img_52937fa8505fb77fd444833271624efd.png

KMP可以在匹配过程中失配的情况下,有效地多往后面跳几个字符,加快匹配速度。
下面先直接给出KMP的算法流程:


img_b65010ffce96ed04d5cac369d7b46269.png
图一(a)
img_44940c0f9866edbdf5d139eb2376e1c2.png
图一(b)
img_f2e6f4bb054ab8b6b7e1c753f6162df2.png
图二(a)
img_9a0cc43cc168439c02bc8f8caceb121b.png
图二(b)

假设现在文本串S匹配到i位置,模式串P匹配到j位置

  • 当前字符匹配成功(即S[i] == P[j],图一),都令k++j++,继续匹配下一个字符;
  • 当前字符匹配失败(即S[i] != P[j],图二),则令 k不变,j = next[j]。此举意味着失配时,模式串P相对于文本串S向右移动了j - next [j]位。

换言之,当匹配失败时,模式串向右移动的位数为:失配字符所在位置 - 失配字符对应的next 值(next 数组的求解会在下文详细阐述),即移动的实际位数为:j - next[j],且此值≥1。


next数组(前缀数组)

每一个模式串P都有有一个固定的next数组,它记录着字符串匹配过程中失配情况下可以向前多跳几个字符,当然它描述的也是子串的对称程度,程度越高,值越大,当然之前可能出现再匹配的机会就更大。

img_0e4e4047bda1e47fc68cf875ad28b91d.png

这个next数组的求法是KMP算法的关键,看到别的地方到处是数学公式推导,我这里用图示的方法方便大家理解。

img_fae95503c99290e391ecd70f8cda1adf.png
  • 红色:模式串P当前已经匹配好的相同前后缀
  • 蓝色:模式串P当前匹配的位置,就是j
  • 橙色:模式串P当前匹配的最长前缀的后一位,即为k

如果p[j] == p[k],则皆大欢喜, next[j] = next[j - 1] + 1
如果p[j] != p[k],只能寻找更短的相同前后缀匹配,我们看下图

img_bfbf4609ec3947ef5422e9b9cdab6ad3.png
  • 灰色:当前已经匹配好相同前后缀中的最长公共前后缀
  • 紫色:当前已经匹配好相同前后缀中的前缀的后一位

因为红色部分是已经匹配好的,所以既然第二个的后面为灰色部分,第一个的前面和后面也为灰色部分,接下来对应的,第二个前面的也为灰色部分。

查阅蓝色紫色是否匹配。

此时,又回到最初的那一步(递归),求解某个位置的next值是一个循环过程,不断检查 上一位的最长前缀的后一位.
如果相等next[j] = next[k] + 1,否则 k = next[k]


代码

//优化过后的next 数组求法
void GetNextval(char* p, int next[]) {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1){
        //p[k]表示前缀,p[j]表示后缀  
        if (k == -1 || p[j] == p[k]){
            ++j;
            ++k;
            //较之前next数组求法,改动在下面4行
            if (p[j] != p[k])
                next[j] = k;   //之前只有这一行
            else
                //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else{
            k = next[k];
        }
    }
}

参考链接

目录
相关文章
|
5月前
|
算法
数据结构中的KMP算法及其改进算法
KMP算法通过引入部分匹配表,有效避免了重复计算,从而将字符串匹配的时间复杂度降低到O(m+n)。通过进一步优化next数组,KMP算法的效率得到了进一步提升。对于大规模字符串匹配问题,KMP算法及其改进算法提供了高效的解决方案,是计算机科学领域的经典算法之一。
79 3
|
22天前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
16 0
|
25天前
|
算法
KMP算法
KMP算法
22 0
|
3月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
4月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
106 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
3月前
|
算法
KMP算法
KMP算法
25 0
|
4月前
|
算法 Java
KMP算法详解及其在字符串匹配中的应用
KMP算法详解及其在字符串匹配中的应用
|
5月前
|
人工智能 算法 BI
一篇文章讲明白KMP算法(俗称看毛片算法)
一篇文章讲明白KMP算法(俗称看毛片算法)
53 0
|
5月前
|
算法 Java
Java数据结构与算法:字符串匹配算法之KMP算法
Java数据结构与算法:字符串匹配算法之KMP算法
|
6月前
|
算法