每周一算法之六——KMP字符串匹配算法

简介:

KMP是一种著名的字符串模式匹配算法,它的名称来自三个发明人的名字。这个算法的一个特点就是,在匹配时,主串的指针不用回溯,整个匹配过程中,只需要对主串扫描一遍就可以了。因此适合对大字符串进行匹配。

搜了网上很多KMP的代码下来调试,发现不是下标越界,就是死循环的,相当诡异...最后重新拿起严老师那本《数据结构》来翻,各种费解,有个地方用下标值和字符串下标0的元素做判断,更是诡异了...

过了一天,忽然觉悟了。网上这些代码都是来自《数据结构》或者和他同源的版本的,而它使用的是以下标1为起始的字符串!对这种字符串组织格式,下标0存放的是字符串的长度

可是如今主流的语言,几乎都是用的下标0作为起始,书本上的代码显然没法用,那就自己重写一个吧。

 

算法的原理

字符串匹配嘛,无非就是两个指针,分别指向主串和模式串,然后依次往后移,检查是否一致。在遇到不能匹配的情况时(简称“失配”),一般的方法,就是让两个指针回溯,主串指针往后再移动一位,从头开始匹配。这其中做了很多重复劳动,我们可以分析一下:

可以看到模式串在匹配到下标5时失配了。
我们抓出模式串和主串在前方匹配的5个字符,并在模式串部分的前端主串部分的后端找到了一对最长的相等的字串(不等于原来的串),用阴影标记一下,后面有用。

接着移动模式串,继续匹配:

看出什么规律了么?每次比较,其实都是“abaab”的前端后端的字串进行比较:
第一回是"abaa"vs"baab"
第二回是"aba"vs"aab"
第三回是"ab"vs"ab"
可见,只有在模式串部分的前端主串部分的后端重合的时候,才可能继续匹配。

是这样么?当然是的,因为我们之前找出的是最长的,相等的字串!

这样就能把中间无效的对比步骤省略,主串的指针不变,模式串的指针直接跳到下标2继续匹配。这里的下标2就等于最长相等字串的长度。

接着推广到更一般的情形:
假设主串s,模式串patten,s和patten分别在下标i,j处失配,

如果j>0,那么,
显而易见,'si-k...si-1' = 'patten0...pattenk-1',此串长度为k,故下一步模式串指针应当跳转到下标k继续匹配。
在这里,因为'si-k...si-1' = 'pattenj-k...pattenj-1',得到'patten0...pattenk-1' = 'pattenj-k...pattenj-1',所以给定patten和j的情况下,k的值也是固定的。

如果j=0,那么i应当往后挪一位,j不变,重头匹配

至此,对于给定的patten,可以得到一个j->k的映射关系,记为数组next,其中,k = next[j]:
next[j] = Max{ k | 0<=k<j 并且 'patten0...pattenk-1' = 'pattenj-k...pattenj-1' }
当且仅当j == 0时,next[j] = -1(-1其实是没有意义的,在这里为了计算方便)

 

依照这个定义,已经可以写出一个计算next的弱弱的实现了。不过我先买个关子,先把主串的匹配搞定再说。

 

主串匹配算法

有了之前的分析,主串匹配的代码基本就可以一蹴而就了(Java代码):

复制代码
复制代码
static int Kmp(String s, String patten) {
    int i = 0, j = -1;
    int[] next = GetNext(patten);// 待实现

    while (i < s.length() && j < patten.length()) {
        if (j == -1 || s.charAt(i) == patten.charAt(j)) {
            i++;
            j++;
        } else {
            j = next[j];// 失配时跳转
        }
    }

    if (j == patten.length()) // 完全匹配
        return i - j;

    return -1;
}
复制代码
复制代码

这儿有一处很巧妙地的地方:
next[0]是恒为-1的,所以如果在下标0处失配,则下一次循环j等于-1,i就会在循环中指向下一个字符,j也恢复为0。

 

模式串的next数组生成算法

看下面这张图

假设模式串上的下标i,模式串下的下标j,那么
显然next[5] = 2是由patteni=4 = pattenj=1推出的,
推广到一般的情况,也就是说当patten与自身错位匹配时,当他们在i,j(i>j)处匹配时,
此时可以得到next[i+1] = j+1
如果j = 0时就失配了的话,自然next[i+1]应当等于0

至此,写出代码也就不难了,有些小技巧却要注意一下(Java代码):

复制代码
复制代码
static int[] GetNext(String s) {
    int i = 0, j = -1;
    int[] next = new int[s.length()];
    next[0] = -1; // 这个初始化时必须的

    while( i<s.length()-1)
    {
        if( j == -1 || s.charAt(i) == s.charAt(j))
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];// 当j在下标零处失配,代码会怎么执行呢?
        }
    }
    return next;
}
复制代码
复制代码

 

这个求next数组的方式和KMP算法的主体是不是很像呢?

目录
相关文章
|
4月前
|
算法
【算法】滑动窗口——找到字符串中所有字母异位词
【算法】滑动窗口——找到字符串中所有字母异位词
|
2月前
|
算法
两个字符串匹配出最长公共子序列算法
本文介绍了最长公共子序列(LCS)问题的算法实现,通过动态规划方法求解两个字符串的最长公共子序列,并提供了具体的编程实现细节和示例。
92 1
两个字符串匹配出最长公共子序列算法
|
2月前
|
算法
第四章 KMP算法理论基础
第四章 KMP算法理论基础
20 0
|
2月前
|
算法
KMP算法
KMP算法
35 0
|
4月前
|
算法 C++
A : DS串应用–KMP算法
这篇文章提供了KMP算法的C++实现,包括计算模式串的next数组和在主串中查找模式串位置的函数,用于演示KMP算法的基本应用。
|
4月前
|
算法 Java
掌握算法学习之字符串经典用法
文章总结了字符串在算法领域的经典用法,特别是通过双指针法来实现字符串的反转操作,并提供了LeetCode上相关题目的Java代码实现,强调了掌握这些技巧对于提升算法思维的重要性。
|
5月前
|
自然语言处理 算法 搜索推荐
字符串相似度算法完全指南:编辑、令牌与序列三类算法的全面解析与深入分析
在自然语言处理领域,人们经常需要比较字符串,这些字符串可能是单词、句子、段落甚至是整个文档。如何快速判断两个单词或句子是否相似,或者相似度是好还是差。这类似于我们使用手机打错一个词,但手机会建议正确的词来修正它,那么这种如何判断字符串相似度呢?本文将详细介绍这个问题。
299 1
|
5月前
|
数据采集 算法 JavaScript
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
JavaScript字符串搜索涵盖`indexOf`、`includes`及KMP算法。`indexOf`返回子字符串位置,`includes`检查是否包含子字符串。KMP是高效的搜索算法,尤其适合长模式匹配。示例展示了如何在数据采集(如网页爬虫)中使用这些方法,结合代理IP进行安全搜索。代码示例中,搜索百度新闻结果并检测是否含有特定字符串。学习这些技术能提升编程效率和性能。
131 1
揭开JavaScript字符串搜索的秘密:indexOf、includes与KMP算法
|
4月前
|
算法
KMP算法
KMP算法
31 0
|
4月前
|
算法 C++
惊爆!KPM算法背后的秘密武器:一行代码揭秘字符串最小周期的终极奥义,让你秒变编程界周期大师!
【8月更文挑战第4天】字符串最小周期问题旨在找出字符串中最短重复子串的长度。KPM(实为KMP,Knuth-Morris-Pratt)算法,虽主要用于字符串匹配,但其生成的前缀函数(next数组)也可用于求解最小周期。核心思想是构建LPS数组,记录模式串中每个位置的最长相等前后缀长度。对于长度为n的字符串S,其最小周期T可通过公式ans = n - LPS[n-1]求得。通过分析周期字符串的特性,可证明该方法的有效性。提供的C++示例代码展示了如何计算给定字符串的最小周期,体现了KPM算法在解决此类问题上的高效性。
87 0