一、 前语
记住在咱们初中、高中、四六级的时候都做过英语阅览了解，在做阅览了解的时候时常需要在一篇文章中找到关键词、短语或许句子，这就好比在一段文本中寻觅特定的字符串。假如咱们想要知道某个单词在一篇阅览了解中出现的次数以便于咱们日后温习这个单词，咱们需要怎么做呢？
二、 朴素的形式匹配算法
1、概念
朴素形式匹配算法（Naive Pattern Matching Algorithm）是一种最简略直观的字符串形式匹配办法。该算法的根本思维是从文本的榜首个字符开端，依次比较形式串和文本串中的字符，逐渐滑动形式串，直到找到匹配的子串或许遍历完整个文本。
2、比如
比方咱们需要在一串字符串”askdfgaiusfuabcfuabcuabsui”中找到”abc”，咱们需要怎么做呢？
public class NaivePatternMatching {
public static void main(String[] args) {
String text = "askdfgaiusfuabcfuabcuabsui";
String pattern = "abc";
int position = naivePatternMatching(text, pattern);
if (position != -1) {
System.out.println("Pattern found at position: " + position);
} else {
System.out.println("Pattern not found in the text.");
}
}
private static int naivePatternMatching(String text, String pattern) {
int n = text.length();
int m = pattern.length();
for (int i = 0; i <= n - m; i++) {
int j;
for (j = 0; j < m; j++) {
if (text.charAt(i + j) != pattern.charAt(j)) {
break;
}
}
if (j == m) {
return i;
}
}
return -1;
}
}
在上述比如中咱们运用的就是：朴素的形式匹配算法。
思路如下：
- 初始化变量：
获取文本串
text和形式串pattern的长度，别离记为n和m。
- 循环遍历文本：
运用外层循环从
i = 0开端，直到i = n - m。这是因为在剩下的文本长度小于形式长度时，无需再进行匹配。
- 内层形式匹配循环：
在每个外层循环的方位
i，运用内层循环比较文本和形式的字符。
内层循环变量j从 0 到m-1，对应形式串的每个字符。
假如发现不匹配的字符，跳出内层循环，持续外层循环的下一个方位。
假如一直匹配到内层循环结束，即j == m，表明找到完整的匹配，回来当时方位i。
- 回来结果：
假如外层循环结束都没有找到匹配，回来 -1 表明形式未在文本中找到。
3、利弊
朴素形式匹配算法的优点：
- 简略易懂： 朴素形式匹配算法是一种十分直观和简略了解的算法。它的完成逻辑简略，不触及杂乱的数据结构和算法。
- 简略完成： 因为其简略性，朴素形式匹配算法的完成相对简略，适用于初学者学习算法和数据结构的阶段。
- 适用于短形式串： 在形式串较短的情况下，朴素形式匹配算法或许表现得比较高效，因为在短形式下，算法不会触及过多的字符比较。
朴素形式匹配算法的害处：
- 功率低下： 在处理大规模文本和较长形式串时，朴素形式匹配算法的功率较低。它需要在每个方位都进行完整的形式匹配，导致时刻杂乱度较高。
- 重复比较： 因为算法的简略性，它或许会在文本和形式之间进行大量的重复比较，尤其是在未找到匹配时，导致功能欠安。
- 不适用于大规模数据： 跟着数据规模的增大，朴素形式匹配算法的功能会明显下降，不太适用于处理大型数据集。
- 无法处理形式中的通配符： 关于包括通配符等杂乱形式的情况，朴素形式匹配算法无法有用处理，因为它只是简略地逐字符比较。
三、KMP形式匹配算法
1、概念
KMP（Knuth-Morris-Pratt）形式匹配算法是一种高效的字符串匹配算法，用于在一个文本串中查找是否包括一个形式串。它的首要思维是在匹配进程中充分使用现已匹配过的信息，防止不必要的字符比较，然后提高匹配的功率。
2、关键词
- 最长公共前后缀（LPS）：
关于形式串中的每个方位，找到其前缀和后缀的最长一起部分。这个信息被预处理并存储在一个部分匹配表中。
- 部分匹配表（Partial Match Table）：
部分匹配表是一个数组，记录了形式串中每个方位的最长公共前后缀的长度。它协助算法在匹配进程中越过现已匹配过的部分，防止不必要的比较。
3、根本步骤
-
构建部分匹配表：
- 关于形式串，计算并构建部分匹配表，确定每个方位的最长公共前后缀。
-
匹配进程：
- 在文本串中从左到右逐字符匹配形式串。
- 当发现不匹配时，依据部分匹配表，将形式串向右移动必定的位数，持续匹配。
4、比如
考虑文本串 “ABABCABABCABC” 和形式串 “ABABC”，使用KMP算法：
-
构建部分匹配表：0,0,1,2,00,0,1,2,0
- 方位 1: “A”，无前缀和后缀，长度为 0
- 方位 2: “AB”，无前缀和后缀，长度为 0
- 方位 3: “ABA”，前缀 “A” 和后缀 “A”，长度为 1
- 方位 4: “ABAB”，前缀 “AB” 和后缀 “AB”，长度为 2
- 方位 5: “ABABC”，无前缀和后缀，长度为 0
-
匹配进程：
- 文本串的榜首个字符 “A” 与形式串的榜首个字符匹配。
- 下一个字符 “B” 匹配，持续。
- “A” 不匹配，依据部分匹配表将形式串右移 1 位。
- 持续匹配，找到完整的匹配。
public class KMPAlgorithm {
public static void main(String[] args) {
String text = "ABABCABABCABC";
String pattern = "ABABC";
int position = kmpSearch(text, pattern);
if (position != -1) {
System.out.println("Pattern found at position: " + position);
} else {
System.out.println("Pattern not found in the text.");
}
}
private static int kmpSearch(String text, String pattern) {
int[] lps = computeLPSArray(pattern);
int n = text.length();
int m = pattern.length();
int i = 0;
int j = 0;
while (i < n) {
if (pattern.charAt(j) == text.charAt(i)) {
i++;
j++;
}
if (j == m) {
return i - j;
} else if (i < n && pattern.charAt(j) != text.charAt(i)) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1;
}
private static int[] computeLPSArray(String pattern) {
int m = pattern.length();
int[] lps = new int[m];
int len = 0;
int i = 1;
while (i < m) {
if (pattern.charAt(i) == pattern.charAt(len)) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
}
5、利弊
KMP形式匹配算法的优势：
- 高效的匹配进程： KMP算法通过部分匹配表的预处理，防止了在形式匹配的进程中对文本串中现已匹配的部分进行不必要的重复比较，然后提高了匹配功率。
- 适用于大规模数据： 相较于朴素形式匹配算法，KMP在处理大规模文本和形式串时表现更为超卓。它的时刻杂乱度为O(N+M)，其间N为文本长度，M为形式长度。
- 削减字符比较次数： 通过使用现已匹配的信息，KMP算法在每次不匹配时能够越过必定的字符，削减了字符比较的次数。
- 适用于通用字符串匹配问题： KMP算法的思维能够扩展应用到通用的字符串匹配问题，例如在DNA序列等范畴。
KMP形式匹配算法的劣势：
- 较杂乱的完成： 相关于朴素形式匹配算法，KMP算法的完成稍显杂乱，触及到构建部分匹配表和多个指针的维护。
- 额定的空间开销： KMP算法需要额定的空间来存储部分匹配表，关于一些对内存要求较高的场景或许不太适用。
- 不适用于一些特定场景： 在一些特定场景下，例如形式串较短、数据量较小的情况下，KMP算法的优势或许不如其他算法明显。
总结
必定要多思考，假如人永久待在舒适圈的话，人永久不会成长。共勉
觉得作者写的不错的，值得你们学习的话，就请点一个免费的赞吧！这个对我来说真的很重要。૮(ᵔ ᵕ ᵔ)ა
