朴素模式匹配算法

Posted in 2010-01-23 8:41 PMJulius ChenNo Comments »

朴素模式匹配算法又称简单匹配算法或Brute-Force算法，它是字符串模式匹配中比较简单的一种算法。它从主串的第一个字符开始进行模式匹配，依次比较主串和模式串中的每个字符，若比较全部相等（模式匹配成功），则返回模式串中第一个字符在主串中的位置，否则主串指针从比较失败的字符处回溯到第二个字符开始重新和模式串进行匹配，这样依此下去，直到和模式串匹配成功或到主串的末尾（匹配不成功）为止。

朴素模式匹配算法的C/C++代码实现：

  1. // 定义一个字符串结构体
  2. typedef struct  {
  3.     char data[MAX_SIZE];
  4.     int length;
  5. } string;
  6.  
  7. int BruteForce(string s, string t)
  8. {
  9.     int i = 0, j = 0;
  10.     while (i < s.length && j < t.length) {
  11.         if (s[i] == t[j]) {
  12.             i++;
  13.             j++;
  14.         } 
  15.         else {
  16.             i = i - j + 1; // 主串指针回溯
  17.             j = 0;
  18.         }
  19.     }
  20.    
  21.     if (j > t.length)
  22.         return i - t.length;
  23.     else
  24.         return -1;
  25. }
  26.  
  27. // 另外也可以参考一下C语言库函数
  28. // 中具有相同功能的strstr()函数的实现
  29. char *strstr(const char *s1, const char *s2)
  30. {
  31.     int l1, l2;
  32.    
  33.     l2 = strlen(s2);
  34.     if (!l2)
  35.         return (char *)s1;
  36.     l1 = strlen(s1);
  37.     while (l1 >= l2) {
  38.         l1--;
  39.         if (!memcmp(s1, s2, l2))
  40.             return (char *)s1;
  41.         s1++;
  42.     }
  43.     return NULL;
  44. }

朴素模式匹配算法在通常情况下其时间复杂度都近似于O(n+m)，但在最坏情况下（如极端情况：主串aaaaa … 很多个a … aaaaab，模式串aaaaab），由于主串指针需要不停的回溯，因此其时间复杂度需为O(nm)。

Strings, ,

文章若无注明则属原创，转载请以链接形式注明出处。
本文地址：http://www.juliuschen.com/archives/20.html

Leave a Reply