朴素模式搜索算法
数据结构中的朴素模式搜索算法
朴素模式搜索是所有模式搜索算法中最简单的方法。虽然它比暴力破解方法更高效，但它并非最优方法。与暴力破解方法类似，它也需要检查主字符串的所有字符以找到模式。因此，其时间复杂度为O(m*n)，其中"m"表示模式的大小，"n"表示主字符串的大小。此算法仅适用于较小的文本。
朴素模式搜索算法不需要任何预处理阶段。我们可以通过检查一次字符串来找到子字符串。它也不占用额外的空间来执行操作。如果找到匹配项，则模式匹配操作的最终结果将是指定模式的索引，否则为-1。此外，如果所需模式在主字符串中出现多次，此操作可以返回所有索引。
让我们通过一个例子来理解模式匹配问题的输入输出场景 −
输入： main String: "ABAAABCDBBABCDDEBCABC" pattern: "ABC" 输出： Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
示例
在下面的示例中，我们将演示如何应用简单的方法来解决模式匹配问题。
#include<stdio.h>
#include<string.h>
// 寻找模式的方法
void naiveFindPatrn(char* mainString, char* pattern, int array[], int *index) {
int patLen = strlen(pattern);
int strLen = strlen(mainString);
// 外层 for 循环
for(int i = 0; i<=(strLen - patLen); i++) {
int j;
// 检查模式的每个字符
for(j = 0; j<patLen; j++) {
if(mainString[i+j] != pattern[j])
break;
}
// 打印找到的模式的索引
if(j == patLen) {
(*index)++;
array[(*index)] = i;
}
}
}
// 主方法开始
int main() {
// main string
char mainString[] = "ABAAABCDBBABCDDEBCABC";
// 找到模式
char pattern[] = "ABC";
int locArray[strlen(mainString)];
int index = -1;
naiveFindPatrn(mainString, pattern, locArray, &index);
// 打印索引
for(int i = 0; i <= index; i++) {
printf("Pattern found at position: %d
", locArray[i]);
}
return 0;
}
#include<iostream>
using namespace std;
// 寻找模式的方法
void naiveFindPatrn(string mainString, string pattern, int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
// 外层 for 循环
for(int i = 0; i<=(strLen - patLen); i++) {
int j;
// 检查模式的每个字符
for(j = 0; j<patLen; j++) {
if(mainString[i+j] != pattern[j])
break;
}
// 打印找到的模式的索引
if(j == patLen) {
(*index)++;
array[(*index)] = i;
}
}
}
// 主方法开始
int main() {
// main string
string mainString = "ABAAABCDBBABCDDEBCABC";
// 找到模式
string pattern = "ABC";
int locArray[mainString.size()];
int index = -1;
naiveFindPatrn(mainString, pattern, locArray, &index);
// 打印索引
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}
public class Main {
// 寻找模式的方法
static void naiveFindPatrn(String mainString, String pattern, int[] array) {
int patLen = pattern.length();
int strLen = mainString.length();
int index = 0;
// 外层 for 循环
for(int i = 0; i <= (strLen - patLen); i++) {
int j;
// 检查模式的每个字符
for(j = 0; j < patLen; j++) {
if(mainString.charAt(i+j) != pattern.charAt(j))
break;
}
// 打印找到的模式的索引
if(j == patLen) {
array[index] = i;
index++;
}
}
}
// 主方法开始
public static void main(String[] args) {
// main string
String mainString = "ABAAABCDBBABCDDEBCABC";
// 找到模式
String pattern = "ABC";
int[] locArray = new int[mainString.length()];
naiveFindPatrn(mainString, pattern, locArray);
// 打印索引
for(int i = 0; i < locArray.length && locArray[i] != 0; i++) {
System.out.println("Pattern found at position: " + locArray[i]);
}
}
}
# 搜索模式的方法
def naiveFindPatrn(mainString, pattern):
patLen = len(pattern)
strLen = len(mainString)
indices = []
# 外层 for 循环
for i in range(strLen - patLen + 1):
j = 0
# 检查模式的每个字符
for j in range(patLen):
if mainString[i+j] != pattern[j]:
break
# 打印找到的模式的索引
if j == patLen - 1 and mainString[i+j] == pattern[j]:
indices.append(i)
return indices
# main method starts
if __name__ == "__main__":
# main string
mainString = "ABAAABCDBBABCDDEBCABC"
# 找到模式
pattern = "ABC"
indices = naiveFindPatrn(mainString, pattern)
# 打印索引
for i in indices:
print("Pattern found at position:", i)
输出
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
