帮忙做网站的协议,上门做网站公司哪家好,网站高速下载如何做,网络广告包括tip#xff1a;作为程序员一定学习编程之道#xff0c;一定要对代码的编写有追求#xff0c;不能实现就完事了。我们应该让自己写的代码更加优雅#xff0c;即使这会费时费力。
推荐#xff1a;体系化学习Java#xff08;Java面试专题#xff09; 文章目录 一、什么是 …tip作为程序员一定学习编程之道一定要对代码的编写有追求不能实现就完事了。我们应该让自己写的代码更加优雅即使这会费时费力。
推荐体系化学习JavaJava面试专题 文章目录 一、什么是 KMP 算法二、KMP 算法的作用三、KMP 算法的原理四、用 java 写一个 KMP 算法的例子五、KMP 预处理的计算过程六、KMP 算法和 String.indexOf 的对比六、KMP 算法和 String.indexOf 的性能对比数据 一、什么是 KMP 算法
KMP算法全称为Knuth-Morris-Pratt算法是一种字符串匹配算法。它的基本思想是当出现字符串不匹配时可以知道一部分文本内容是一定匹配的可以利用这些信息避免重新匹配已经匹配过的文本。这种算法的时间复杂度为O(nm)其中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[j1]的值设为i1否则我们需要将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(nm) O(nm)其中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 数组。
模式串自我匹配
首先我们需要对模式串进行自我匹配以确定每个位置的最长公共前后缀长度。具体来说我们从模式串的第二个字符开始依次将其与前面的字符进行比较记录其与前面字符的最长公共前后缀长度。例如对于模式串 “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。
计算 next 数组
在模式串自我匹配完成后我们可以根据自我匹配的结果计算 next 数组。具体来说对于模式串中的第 i 个字符其 next 值为最长公共前后缀的长度加一即 next[i] len[i] 1其中 len[i] 表示模式串中以第 i 个字符结尾的最长公共前后缀长度。需要注意的是next[0] 的值为 0next[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(mn)其中 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 算法耗时msindexOf 方法耗时ms1001011100501210010014100010111000502231000100311810000102110000501315610000100261211
从上表可以看出当文本串和模式串长度相差不大时KMP 算法的效率与 indexOf 方法相当但当模式串很长或者文本串很短时KMP 算法的效率明显高于 indexOf 方法。
