C语言实现朴素模式匹配算法

C语言中的模式匹配− 我们需要查找一个字符串是否出现在另一个字符串中，例如，字符串“algorithm”出现在字符串“naive algorithm”中。如果找到，则显示其位置（即出现的位置）。我们将创建一个接收两个字符数组并返回匹配位置（匹配则返回位置，否则返回-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

我们使用朴素模式搜索算法来解决这个问题。此算法适用于较小的文本。朴素算法是一种简单但低效的方法，用于查找一个字符串是否出现在另一个字符串中，它逐一检查字符串可能出现的所有位置。

朴素算法的时间复杂度为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 
", i);
   }
   return 0;
}

输出

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

更新于: 2019年12月24日

7K+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告