C程式的樸素模式搜尋演算法

C 中的模式匹配- 我們必須查找一個字串是否存在於另一個字串中，例如，字串「algorithm」存在於字串“naive algorithm”中。如果是找到，然後顯示它的位置（即它的位置）。我們傾向於創建一個函數，它接收 2 個字元數組，如果匹配則返回位置，否則返回 -1。

Input: txt = "HERE IS A NICE CAP"
   pattern = "NICE"
Output: Pattern found at index 10
Input: txt = "XYZXACAADXYZXYZX"
   pattern = "XYZX"
Output: Pattern found at index 0
   Pattern found at index 9
   Pattern found at index 12

我們正在透過樸素模式搜尋來解決這個問題。該演算法對於較小的文字很有用。 Naive 是一種簡單而低效的方法，要查看字串在另一個字串中出現的位置，就要逐一檢查它可能出現的每個位置，以檢查它是否存在。

Naive 演算法的時間複雜度為O(mn)，其中m是要搜尋的模式的大小，n是容器字串的大小。

模式搜尋是電腦科學中非常關鍵的問題。每當我們在記事本/word檔案或瀏覽器或資料庫或某些資訊中尋找字串時， 模式搜尋演算法用於顯示搜尋結果。

演算法

naive_algorithm(pattern, text)

#輸入− 文字與模式

##輸出#−模式在文字中出現的位置

Start
   pat_len := pattern Size
   str_len := string size
   for i := 0 to (str_len - pat_len), do
      for j := 0 to pat_len, do
         if text[i+j] ≠ pattern[j], then
         break
   if j == patLen, then
   display the position i, as there pattern found
End

範例

 即時示範

#include <stdio.h>
#include <string.h>
int main (){
   char txt[] = "tutorialsPointisthebestplatformforprogrammers";
   char pat[] = "a";
   int M = strlen (pat);
   int N = strlen (txt);
   for (int i = 0; i <= N - M; i++){
      int j;
      for (j = 0; j < M; j++)
         if (txt[i + j] != pat[j])
      break;
      if (j == M)
         printf ("Pattern matches at index %d </p><p>", i);
   }
   return 0;
}

輸出

Pattern matches at 6
Pattern matches at 25
Pattern matches at 39

以上是C程式的樸素模式搜尋演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！