樸素模式匹配演算法

資料結構中的樸素模式匹配演算法

樸素模式匹配是各種模式匹配演算法中最簡單的一種方法。雖然它比暴力方法更有效率，但它並不是最優的方法。與暴力法一樣，它也依次檢查主字串的所有字元以查詢模式。因此，其時間複雜度為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

列印頁面