天真模式搜索
天真的模式搜索是其他模式搜索算法中最简单的方法。它检查模式中主字符串的所有字符。该算法对较小的文本很有帮助。它不需要任何预处理阶段。我们可以通过一次检查字符串来找到子字符串。它还不占用额外的空间来执行操作。
朴素模式搜索方法的时间复杂度为O（m*n）。m是样式的大小，n是主字符串的大小。
输入输出
Input: Main String: “ABAAABCDBBABCDDEBCABC”, pattern: “ABC” Output: Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18
算法
naivePatternSearch(pattern, text)
输入-文字和图案
输出- 位置，文本中存在模式
Begin
patLen := pattern Size
strLen := string size
for i := 0 to (strLen - patLen), do
for j := 0 to patLen, do
if text[i+j] ≠ pattern[j], then
break the loop
done
if j == patLen, then
display the position i, as there pattern found
done
End示例
#include<iostream>
using namespace std;
void naivePatternSearch(string mainString, string pattern, int array[], int *index) {
int patLen = pattern.size();
int strLen = mainString.size();
for(int i = 0; i<=(strLen - patLen); i++) {
int j;
for(j = 0; j<patLen; j++) { //check for each character of pattern if it is matched
if(mainString[i+j] != pattern[j])
break;
}
if(j == patLen) { //the pattern is found
(*index)++;
array[(*index)] = i;
}
}
}
int main() {
string mainString = "ABAAABCDBBABCDDEBCABC";
string pattern = "ABC";
int locArray[mainString.size()];
int index = -1;
naivePatternSearch(mainString, pattern, locArray, &index);
for(int i = 0; i <= index; i++) {
cout << "Pattern found at position: " << locArray[i]<<endl;
}
}输出结果
Pattern found at position: 4 Pattern found at position: 10 Pattern found at position: 18