朴素模式匹配算法

数据结构中的朴素模式匹配算法

朴素模式匹配是各种模式匹配算法中最简单的一种方法。虽然它比暴力方法更有效率，但它并不是最优的方法。与暴力法一样，它也依次检查主字符串的所有字符以查找模式。因此，其时间复杂度为O(m*n)，其中'm'是模式的大小，'n'是主字符串的大小。此算法仅适用于较小的文本。

朴素模式匹配算法不需要任何预处理阶段。我们可以通过一次检查字符串来找到子字符串。它也不占用额外的空间来执行操作。如果找到匹配项，则模式匹配操作的最终结果将是指定模式的索引，否则为-1。此外，如果所需模式在主字符串中多次出现，此操作可以返回所有索引。

让我们通过一个例子来了解模式匹配问题的输入输出场景：

Input:
main String: "ABAAABCDBBABCDDEBCABC" 
pattern: "ABC"
Output:
Pattern found at position: 4
Pattern found at position: 10
Pattern found at position: 18

示例

在下面的示例中，我们将演示如何应用朴素方法来解决模式匹配问题。

C C++ Java Python

#include<stdio.h>
#include<string.h>
// method to search for pattern
void naiveFindPatrn(char* mainString, char* pattern, int array[], int *index) {
   int patLen = strlen(pattern);
   int strLen = strlen(mainString);
   // outer for loop 
   for(int i = 0; i<=(strLen - patLen); i++) {
      int j;
      // to check for each character of pattern 
      for(j = 0; j<patLen; j++) {      
         if(mainString[i+j] != pattern[j])
            break;
      }
      // to print the index of the pattern is found
      if(j == patLen) {    
         (*index)++;
         array[(*index)] = i;
      }
   }
}
// main method starts
int main() {
   // main string
   char mainString[] = "ABAAABCDBBABCDDEBCABC";
   // pattern to be found
   char pattern[] = "ABC";
   int locArray[strlen(mainString)];
   int index = -1;
   naiveFindPatrn(mainString, pattern, locArray, &index);
    // to print the indices
   for(int i = 0; i <= index; i++) {
      printf("Pattern found at position: %d\n", locArray[i]);
   }
   return 0;
}

#include<iostream>
using namespace std;
// method to search for pattern
void naiveFindPatrn(string mainString, string pattern, int array[], int *index) {
   int patLen = pattern.size();
   int strLen = mainString.size();
   // outer for loop 
   for(int i = 0; i<=(strLen - patLen); i++) {
      int j;
      // to check for each character of pattern 
      for(j = 0; j<patLen; j++) {      
         if(mainString[i+j] != pattern[j])
            break;
      }
      // to print the index of the pattern is found
      if(j == patLen) {    
         (*index)++;
         array[(*index)] = i;
      }
   }
}
// main method starts
int main() {
   // main string
   string mainString = "ABAAABCDBBABCDDEBCABC";
   // pattern to be found
   string pattern = "ABC";
   int locArray[mainString.size()];
   int index = -1;
   naiveFindPatrn(mainString, pattern, locArray, &index);
    // to print the indices
   for(int i = 0; i <= index; i++) {
      cout << "Pattern found at position: " << locArray[i]<<endl;
   }
}

public class Main {
   // method to search for pattern
   static void naiveFindPatrn(String mainString, String pattern, int[] array) {
      int patLen = pattern.length();
      int strLen = mainString.length();
      int index = 0;
      // outer for loop 
      for(int i = 0; i <= (strLen - patLen); i++) {
         int j;
         // to check for each character of pattern 
         for(j = 0; j < patLen; j++) {      
            if(mainString.charAt(i+j) != pattern.charAt(j))
               break;
         }
         // to print the index of the pattern is found
         if(j == patLen) {    
            array[index] = i;
            index++;
         }
      }
   }
   // main method starts
   public static void main(String[] args) {
      // main string
      String mainString = "ABAAABCDBBABCDDEBCABC";
      // pattern to be found
      String pattern = "ABC";
      int[] locArray = new int[mainString.length()];
      naiveFindPatrn(mainString, pattern, locArray);
      // to print the indices
      for(int i = 0; i < locArray.length && locArray[i] != 0; i++) {
         System.out.println("Pattern found at position: " + locArray[i]);
      }
   }
}

# method to search for pattern
def naiveFindPatrn(mainString, pattern):
   patLen = len(pattern)
   strLen = len(mainString)
   indices = []
   # outer for loop 
   for i in range(strLen - patLen + 1):
      j = 0
      # to check for each character of pattern 
      for j in range(patLen):      
         if mainString[i+j] != pattern[j]:
            break
      # to print the index of the pattern is found
      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 to be found
   pattern = "ABC"
   indices = naiveFindPatrn(mainString, pattern)
   # to print the indices
   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

打印页面