DSA - 模式搜索
什么是模式搜索？
模式搜索/匹配算法是一种用于在给定文本中定位或查找特定模式或子字符串的技术。其基本思想是在指定的数据结构中查找特定模式的所有出现位置。例如，给定一个数字数组 [1, 2, 3, 4, 5, 6, 3, 4, 9]，我们需要找到模式 [3, 4] 在数组中出现的所有位置。答案是索引号 2 和 6。
模式搜索算法如何工作？
有多种以不同方式工作的模式搜索算法。设计这类算法的主要目标是降低时间复杂度。传统方法可能需要花费大量时间才能完成较长文本的模式搜索任务。
如果我们说传统方法，实际上是指解决模式搜索问题的蛮力法。让我们看看它是如何工作的 −
将模式滑过文本。
逐个比较每个字符。
如果所有字符都匹配，则我们找到了匹配项。
如果不是，则将模式向右移动一个位置，并重复此过程，直到到达文本末尾或找到匹配项。
请记住，暴力破解是解决字符串匹配或搜索最简单的方法，但它也是最慢、效率最低的方法。该算法的时间复杂度为O(nm)，其中"n"表示文本长度，"m"表示模式长度。这意味着在最坏情况下，我们必须将文本中的每个字符与模式中的每个字符进行比较，如果 n 和 m 较大，则速度会非常慢。下一节还会提到其他算法。
示例
在本例中，我们将实际演示如何在各种编程语言中运用暴力方法解决模式匹配问题。
#include <stdio.h>
#include <string.h>
// method to find match
void findMatch(char *orgText, char *pattern) {
int n = strlen(orgText);
int m = strlen(pattern);
// 逐一比较文本和模式
for (int i = 0; i <= n-m; i++) {
int j = 0;
while (j < m && orgText[i+j] == pattern[j]) {
j++;
}
// 如果找到则打印结果
if (j == m) {
printf("Oohhoo! Match found at index: %d
", i);
return;
}
}
// 如果没有找到
printf("Oopps! No match found
");
}
int main() {
// 原始文本
char orgText[] = "Tutorials Point";
// 待匹配的模式
char pattern[] = "Point";
// 方法调用
findMatch(orgText, pattern);
return 0;
}
#include <iostream>
#include <string>
using namespace std;
// 查找匹配的方法
void findMatch(string orgText, string pattern) {
int n = orgText.length();
int m = pattern.length();
// 逐一比较文本和模式
for (int i = 0; i <= n-m; i++) {
int j = 0;
while (j < m && orgText[i+j] == pattern[j]) {
j++;
}
// 如果找到则打印结果
if (j == m) {
cout << "Oohhoo! Match found at index: " << i << endl;
return;
}
}
// 如果没有找到
cout << "Oopps! No match found" << endl;
}
int main() {
// 原始文本
string orgText = "Tutorials Point";
// 待匹配的模式
string pattern = "Point";
// 方法调用
findMatch(orgText, pattern);
return 0;
}
public class PattrnMatch {
public static void main(String[] args) {
// 原文
String orgText = "Tutorials Point";
// 要匹配的模式
String pattern = "Point";
// 方法调用
findMatch(orgText, pattern);
}
// 方法来查找匹配
public static void findMatch(String orgText, String pattern) {
int n = orgText.length();
int m = pattern.length();
// 逐一比较文本和模式
for (int i = 0; i <= n-m; i++) {
int j = 0;
while (j < m && orgText.charAt(i+j) == pattern.charAt(j)) {
j++;
}
// 如果找到则打印结果
if (j == m) {
System.out.println("Oohhoo! Match found at index: " + i);
return;
}
}
// 如果没有找到
System.out.println("Oopps! No match found");
}
}
# 查找匹配的方法
def findMatch(orgText, pattern):
n = len(orgText)
m = len(pattern)
# 逐一比较文本和模式
for i in range(n-m+1):
j = 0
while j < m and orgText[i+j] == pattern[j]:
j += 1
# 如果找到则打印结果
if j == m:
print("Oohhoo! Match found at index:", i)
return
# 如果没有找到
print("Oopps! No match found")
# 原文
orgText = "Tutorials Point"
# 待匹配的模式
pattern = "Point"
# 方法调用
findMatch(orgText, pattern)
输出
Oohhoo! Match found at index: 10
数据结构中的模式搜索算法
各种模式搜索技术可以应用于数据结构来检索某些模式。只有当模式搜索操作返回所需元素或其索引时，才称其成功，否则，操作视为失败。
以下是本教程中将介绍的模式搜索算法列表 −
- 朴素模式搜索算法
- Knuth-Morris-Pratt 算法
- Boyer Moore 算法
- 有限自动机算法的高效构建
- Aho-Corasick 算法
- 后缀数组算法
- Kasai 算法
- Manacher 算法算法
- Rabin-Karp 算法
- Z 算法
模式搜索算法的应用
模式搜索算法的应用如下 −
- 生物信息学 − 它是一个应用模式搜索算法来分析生物数据（例如 DNA 和蛋白质结构）的领域。
- 文本处理 − 文本处理涉及从文档集合中查找字符串的任务。它对于抄袭检测、拼写和语法检查、搜索引擎查询等至关重要。
- 数据安全 − 模式匹配算法可用于建立恶意软件检测和密码识别系统，从而实现数据安全。
- 情感分析 − 通过匹配或检测词语的语气，我们可以分析用户的口音、情绪和情感。
- 推荐系统 − 我们还可以通过模式匹配算法分析视频、音频或任何博客的内容，从而进一步帮助推荐其他内容。
