########################################
串
########################################

朴素字符串匹配算法
****************************************

性能如下：

============== ====================
最优时间复杂度 :math:`O(m)`
最坏时间复杂度 :math:`O(m\times n)`
平均时间复杂度 :math:`O(m\times n)`
============== ====================

字符串匹配最简单的算法就是朴素字符串匹配算法，其过程如下：

- 主串和子串匹配时， :math:`i,j` 指针同时进一
- 主传和子串失配时， :math:`i=i-j+1, j=0`

在字符串匹配过程中，由于子串的失配。主传指针 :math:`i` 持续向前回溯，其简单实现如下：

.. code-block:: c

   int strMatch(const char *mainStr, const char *subStr) {
   // 计算主串长度
   int mainLen = strlen(mainStr);
   // 计算子串长度
   int subLen = strlen(subStr);

   if (subLen > mainLen) return -1;
   int i = 0, j = 0;
   while (i < mainLen && (j < subLen)) {
      if (mainStr[i] == subStr[j]) {
         // 主串和子串匹配时指针同时向后移一位
         ++i; ++j;
      } else {
         // 主串和子串失配时指针向前回溯
         i=i-j+1; j = 0;
      }
   }
   if (j == subLen) return i-j;
   return -1;
   }

根据算法导论，我们可以得到一个更加简要的写法：

.. code-block:: cpp

   bool strCmp(const char* a, size_t aBegin, const char* b, size_t bBegin, size_t len) {
      for(size_t i = 0; i < len; ++i) {
         if(a[aBegin + i] != b[bBegin + i]) return false;
      }
      return true;
   }

   int NATIVE_STRING_MATCHER(const char* T, const char* P) {
      size_t n = strlen(T) - 1;
      size_t m = strlen(P) - 1;
      for(size_t s = 0; s <= (n - m); ++s) {
         if(strCmp(P, 1, T, s + 1, m)) return (s + 1);
      }
      return -1;
   }

算法导论中数组的起始是零

KMP 匹配算法
****************************************

KMP 算法的性能如下：

============== ==============
平均时间复杂度 :math:`O(n+m)`
============== ==============

KMP 算法实现的核心是求解 next 数组，这部分内容相对而言比较简单：

.. code-block:: c


   int *CountNext(const char *P) {
      int *next = (int*)malloc(strlen(P) * sizeof(int));
      next[0] = 0;
      int i = 1, j = 0;
      for (int i = 1; i < strlen(P); ++i) {
         if (P[i] == P[j]) {
            // 如果匹配，next[i] = next[i-1]+1
            // 这时候说明 P[0:j] == P [x:i]
            // 这里 x 是将 i 向前推时 next 第一个不为零的位置
            next[i] = next[i - 1] + 1;
            ++j;
         } else {
            // 如果发生失配，就将 j 指针移至开头
            j = 0;
            next[i] = 0;
         }
      }
      return next;
   }

KMP 匹配和暴力匹配唯一的区别就是 i 指针不再回溯，只有 j 指针会回溯：

.. code-block:: cpp

   int KMP(const char *T, const char *P) {
      int *next = CountNext(P);
      const int n = strlen(T);
      const int m = strlen(P);
      int i = 0, j = 0;
      for (; i < n && j < m; ++i) {
         if (T[i] == P[j]) ++j;
         else j = next[j];
      }
      if (j == m) return i - j;
      return -1;
   }

.. admonition:: 附记

   尽管这里只介绍了暴力匹配和 KMP 匹配算法，但是现实中还有其他比较好的算法，其性能有些甚至要优于 KMP 算法。参见 :doc:`字符串匹配算法总结`