天真模式搜索

天真的模式搜索是其他模式搜索算法中最简单的方法。它检查模式中主字符串的所有字符。该算法对较小的文本很有帮助。它不需要任何预处理阶段。我们可以通过一次检查字符串来找到子字符串。它还不占用额外的空间来执行操作。

朴素模式搜索方法的时间复杂度为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