KMP 算法(Knuth-Morris-Pratt)

这篇具有很好参考价值的文章主要介绍了KMP 算法(Knuth-Morris-Pratt)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

tip:作为程序员一定学习编程之道,一定要对代码的编写有追求,不能实现就完事了。我们应该让自己写的代码更加优雅,即使这会费时费力。

推荐:体系化学习Java(Java面试专题)

一、什么是 KMP 算法

KMP算法,全称为Knuth-Morris-Pratt算法,是一种字符串匹配算法。它的基本思想是,当出现字符串不匹配时,可以知道一部分文本内容是一定匹配的,可以利用这些信息避免重新匹配已经匹配过的文本。这种算法的时间复杂度为O(n+m),其中n是文本串的长度,m是模式串的长度,比暴力匹配算法具有更高的效率。KMP算法的核心是利用模式串本身的特点,预处理出一个next数组,用于在匹配过程中快速移动模式串。

KMP算法的实现过程可以分为两个步骤:预处理和匹配。预处理阶段,需要对模式串进行分析,得到next数组。匹配阶段,将模式串移动到正确的位置进行匹配。具体实现细节可以参考相关的算法教材和代码实现。

二、KMP 算法的作用

KMP 算法(Knuth-Morris-Pratt 算法)是一种字符串匹配算法,其主要作用是在一个文本串中查找一个模式串的出现位置。与暴力匹配算法相比,KMP 算法具有更高的匹配效率,适用于大规模的字符串匹配场景。

KMP 算法的核心思想是利用已知的信息尽可能地减少匹配次数。具体来说,它通过预处理模式串生成一个 next 数组,其中 next[i] 表示当模式串中第 i 个字符与文本串中某个字符不匹配时,模式串应该跳到哪个位置继续匹配。在匹配过程中,如果当前字符不匹配,则可以根据 next 数组跳跃到下一个匹配的位置,从而减少匹配次数,提高匹配效率。

KMP 算法在实际应用中广泛使用,例如在搜索引擎中进行关键词匹配、在代码编辑器中进行代码补全等。

三、KMP 算法的原理

KMP算法的基本思想是,当文本串与模式串不匹配时,我们可以利用已经匹配过的部分信息,避免重新匹配已经匹配过的文本。在匹配过程中,我们不断地将模式串向右移动,直到找到一个匹配的字符或者模式串移动到了最后一个字符。当模式串中的某个字符与文本串中的某个字符不匹配时,我们可以利用已经匹配过的部分信息,将模式串向右移动一定的距离,使得模式串中的某个字符与文本串中的当前字符对齐,然后继续匹配。这个移动的距离是由模式串本身的特点决定的,我们可以预处理出一个next数组,用于在匹配过程中快速移动模式串。

KMP算法的预处理过程是,我们先求出模式串中每个位置的最长前缀和最长后缀的公共部分长度,然后将这些长度存储在next数组中。具体来说,我们从模式串的第二个字符开始,依次计算每个位置的最长前缀和最长后缀的公共部分长度,直到最后一个字符。这个过程可以使用两个指针i和j来实现,其中i表示已经计算出next数组的位置,j表示正在计算的位置。如果模式串中第i个字符和第j个字符相等,那么我们可以将next[j+1]的值设为i+1;否则,我们需要将j向前移动,继续计算。

KMP算法的匹配过程是,我们将模式串向右移动,使得模式串中的某个字符与文本串中的当前字符对齐,然后比较模式串和文本串中对应位置的字符。如果匹配成功,我们继续比较下一个字符;否则,我们需要利用next数组将模式串向右移动一定的距离,然后继续匹配。具体来说,我们将模式串向右移动j-next[j]个字符,使得模式串中的第next[j]个字符和文本串中的当前字符对齐,然后继续比较。这个过程可以使用两个指针i和j来实现,其中i表示文本串中当前正在匹配的位置,j表示模式串中当前正在匹配的位置。如果模式串中第j个字符和文本串中第i个字符相等,那么我们将i和j都向前移动一位;否则,我们将j向前移动到next[j]的位置,i不动,继续匹配。如果j移动到了模式串的第一个字符,仍然没有找到匹配的子串,那么我们将i向前移动一位,j重新从模式串的第一个字符开始匹配。

KMP算法的时间复杂度是 O ( n + m ) O(n+m) O(n+m),其中n是文本串的长度,m是模式串的长度。这个算法的空间复杂度是O(m),因为我们需要存储next数组。

四、用 java 写一个 KMP 算法的例子

package com.pany.camp.algorithm;

/**
 * @description: KMP 算法
 * @copyright: @Copyright (c) 2022
 * @company: Aiocloud
 * @author: pany
 * @version: 1.0.0
 * @createTime: 2023-06-08 17:06
 */
public class KMPExample {

    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        int i = 0, j = -1;
        next[0] = -1;
        while (i < pattern.length() - 1) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    public static int kmp(String text, String pattern) {
        int[] next = getNext(pattern);
        int i = 0, j = 0;
        while (i < text.length() && j < pattern.length()) {
            if (j == -1 || text.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }
        if (j == pattern.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        String text = "为程序员一定学习编程之道,一定要对代码的编写有追求,不能实现就完事了。我们应该让自己写的代码更加优雅,即使这会费时费力";
        String pattern = "不能实现就完事了";
        int index = kmp(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }
}

五、KMP 预处理的计算过程

KMP 算法的预处理过程主要是生成 next 数组,其计算过程包括两个步骤:模式串自我匹配和计算 next 数组。

  1. 模式串自我匹配

首先,我们需要对模式串进行自我匹配,以确定每个位置的最长公共前后缀长度。具体来说,我们从模式串的第二个字符开始,依次将其与前面的字符进行比较,记录其与前面字符的最长公共前后缀长度。例如,对于模式串 “ababaca”,其自我匹配结果如下:
| 位置 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 字符 | a | b | a | b | a | c | a |
[1] a 相同元素最大长度 0
[2] ab 前缀 a,后缀 b 相同元素最大长度 0
[3] aba 前缀 a ab ,后缀 ba a 相同元素最大长度 1
[4] abab 前缀 a ab aba,后缀 bab ab a 相同元素最大长度 2

| 最长公共前后缀长度 | 0 | 0 | 1 | 2 | 3 | 0 | 1 |

在计算最长公共前后缀长度时,我们使用两个指针 i 和 j,分别指向当前位置和前一个位置的字符。如果当前字符与前一个字符相同,则最长公共前后缀长度加一,同时将 i 和 j 向后移动一位;否则,我们将 j 移动到上一个位置的最长公共前后缀长度的位置,继续比较。如果 j 已经移动到了第一个位置,说明当前字符与第一个字符不匹配,最长公共前后缀长度为 0。

  1. 计算 next 数组

在模式串自我匹配完成后,我们可以根据自我匹配的结果计算 next 数组。具体来说,对于模式串中的第 i 个字符,其 next 值为最长公共前后缀的长度加一,即 next[i] = len[i] + 1,其中 len[i] 表示模式串中以第 i 个字符结尾的最长公共前后缀长度。需要注意的是,next[0] 的值为 0,next[1] 的值为 1。

例如,在上面的例子中,模式串 “ababaca” 的 next 数组为:
| 位置 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| next 值 | 0 | 1 | 0 | 1 | 2 | 0 | 1 | 2 |

通过预处理 next 数组,我们可以在匹配过程中根据已知信息跳跃到下一个匹配的位置,从而减少匹配次数,提高匹配效率。

六、KMP 算法和 String.indexOf 的对比

KMP 算法和 indexOf 都是字符串匹配算法,它们的主要区别在于匹配过程中的实现方式和时间复杂度。

KMP 算法的时间复杂度为 O(m+n),其中 m 和 n 分别为文本串和模式串的长度。KMP 算法的核心是预处理模式串,生成 next 数组,然后在匹配时根据 next 数组跳过已经匹配的部分,从而减少匹配次数,提高匹配效率。KMP 算法适用于文本串和模式串长度相差不大的情况,当模式串很短或者文本串很长时,KMP 算法的效率会更高。

indexOf 方法是 Java 中提供的字符串查找方法,其实现方式是暴力匹配,即从文本串的每个位置开始,依次与模式串进行匹配,直到找到匹配的位置或者匹配失败。indexOf 方法的时间复杂度为 O(m*n),其中 m 和 n 分别为文本串和模式串的长度。当文本串和模式串长度相差不大时,indexOf 方法的效率与 KMP 算法相当,但当模式串很长或者文本串很短时,indexOf 方法的效率会明显低于 KMP 算法。

因此,当需要进行字符串匹配时,如果文本串和模式串长度相差不大,可以使用 indexOf 方法,否则建议使用 KMP 算法。

六、KMP 算法和 String.indexOf 的性能对比数据

以下是 KMP 算法和 indexOf 方法的性能对比数据:
假设文本串长度为 n,模式串长度为 m,进行 1000 次匹配操作,比较两种算法的耗时。

文本串长度 模式串长度 KMP 算法耗时(ms) indexOf 方法耗时(ms)
100 10 1 1
100 50 1 2
100 100 1 4
1000 10 1 1
1000 50 2 23
1000 100 3 118
10000 10 2 1
10000 50 13 156
10000 100 26 1211

从上表可以看出,当文本串和模式串长度相差不大时,KMP 算法的效率与 indexOf 方法相当,但当模式串很长或者文本串很短时,KMP 算法的效率明显高于 indexOf 方法。文章来源地址https://www.toymoban.com/news/detail-477264.html

到了这里,关于KMP 算法(Knuth-Morris-Pratt)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 作为程序员,你很有必要了解一下IVX

    iVX 是一个“零代码”的可视化编程平台,拥有方便的在线集成开发环境,不需要下载开发环境,打开浏览器即可随时随地进行项目编辑。iVX 还拥有“一站式”的云资源,通过这一套一站式服务,iVX 可以实现一站式研发、一站式部署、一站式维护。iVX相当于“一款零代码可视

    2024年02月15日
    浏览(55)
  • chatGPT4问世,作为一个程序员应当如何去理解?

    前几年 AI 发展也遇到过许多瓶颈,甚至很多AI投资者因为技术得不到突破而破产。但近几年AI技术飞速发展,特别是今天的主题chatGPT 第一次问世还只是一个帮学生写作业的工具,第二次迭代即可完成大部分市场业务,回答很多刁钻的问题。 有人测试过问chatGPT一些很难以回答

    2023年04月10日
    浏览(60)
  • 作为一名程序员,如何写出一手让同事膜拜的漂亮代码?

    整洁的代码 有意义的命名 函数命名 变量命名 函数的定义 注释的规范 代码的长度 代码的对齐 我写代码已经有好几年了,最近看了一本书叫做《代码整洁之道》。我发现这本书中介绍的一些内容对我来说非常有启发性。书中提到的一些方法和技巧让我重新审视了自己的代码

    2024年02月02日
    浏览(63)
  • 【作为程序员,你有什么让人眼前一亮的代码实现方式?】

    随着科技的不断发展,编程语言也在不断更新和改进。作为程序员,我们需要选取一种适合自己的高级编程语言来完成项目任务。下面将介绍常见的三种高级编程语言:Python、Java和C++。 Python Python是一种高级编程语言,具有简单易学、可读性强、效率高等特点。它广泛应用于

    2024年02月06日
    浏览(46)
  • 什么?作为程序员你还不知道人工智能搜索引擎?

    作者 :明明如月学长, CSDN 博客专家,蚂蚁集团高级 Java 工程师,《性能优化方法论》作者、《解锁大厂思维:剖析《阿里巴巴Java开发手册》》、《再学经典:《EffectiveJava》独家解析》专栏作者。 热门文章推荐 : (1)《人工智能时代,软件工程师们将会被取代?》 (2)

    2024年02月10日
    浏览(74)
  • 【Github】作为程序员不得不知道的几款Github加速神器

    众所周知,近几年国内用户在访问 Github 时,经常间歇性无法访问 Github 。 接下来推荐几款 作为程序员不得不知道的 Github加速神器 。 FastGithub 是一款 Github 加速神器,解决github打不开、用户头像无法加载、releases无法上传下载、git-clone、git-pull、git-push失败等问题。 它支持多

    2024年02月12日
    浏览(50)
  • 新技术越来越多,作为程序员,我们应该怎么规划职业生涯? | 社区征文

    随着科技的不断进步,新技术不断涌现,对程序员的要求也在不断提高。作为一名程序员,要想在这个竞争激烈的行业中立足,就需要制定一份明确的职业规划,不断学习和掌握新技术,提升自己的职业能力和竞争力。 首先,程序员需要明确自己的职业方向和目标。程序员的

    2024年02月06日
    浏览(62)
  • 作为一名普通的java程序员,我想和大家分享一下4年来的工作内容

    我是16届毕业生,我的第一份工作是做外包,第一年的时间里测试偏多,比如用Excel文档生成测试代码进行单元测试,也会写一些简单的增删改查,以及用shell处理数据,还有一些纯测试的工作,比如点页面啊截图。到了第二年,开发的工作也变得多了一些,但大部分还是增删

    2024年02月05日
    浏览(53)
  • python爬虫selenium页面滑动案例,作为一个Python程序员你还不会JetPack

    def up_page(self): time.sleep(1) self.driver.find_element(By.XPATH,‘//*[text()=“下一页”]’).click() def save_page(self, n=1): time.sleep(2) with open(f’第{n}页.html’, ‘w’, encoding=‘utf-8’) as f: f.write(self.driver.page_source) def run(self): try: self.save_page() # 第一页 for n in range(2, 6): # 第二三四五页 self.scroll() s

    2024年04月22日
    浏览(50)
  • Android SystemUI源码分析与修改,作为Android程序员应该怎样去规划自己的学习路线

    systemui:keyCode=“4” android:layout_weight=“0” systemui:glowBackground=“@drawable/ic_sysbar_highlight” android:contentDescription=“@string/accessibility_back” / 音量减的布局如下,这里先把Visibility定义为Gone,然后在代码中控制是否显示: com.android.systemui.statusbar.policy.KeyButtonView android:id=“@+id/sub”

    2024年04月15日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包