Implement strStr()

描述

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

分析

暴力算法的复杂度是 O(m*n)，代码如下。更高效的的算法有KMP算法、Boyer-Mooer算法和Rabin-Karp算法。面试中暴力算法足够了，一定要写得没有BUG。

暴力匹配

  1. // Implement strStr()
  2. // 暴力解法，时间复杂度O(N*M)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     int strStr(const string& haystack, const string& needle) {
  6.         if (needle.empty()) return 0;
  8.         const int N = haystack.size() - needle.size() + 1;
  9.         for (int i = 0; i < N; i++) {
  10.             int j = i;
  11.             int k = 0;
  12.             while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]) {
  13.                 j++;
  14.                 k++;
  15.             }
  16.             if (k == needle.size()) return i;
  17.         }
  18.         return -1;
  19.     }
  20. };

KMP

  1. // Implement strStr()
  2. // KMP，时间复杂度O(N+M)，空间复杂度O(M)
  3. class Solution {
  4. public:
  5.     int strStr(const string& haystack, const string& needle) {
  6.         return kmp(haystack.c_str(), needle.c_str());
  7.     }
  8. private:
  9.     /*
  10.      * @brief 计算部分匹配表，即next数组.
  11.      *
  12.      * @param[in] pattern 模式串
  13.      * @param[out] next next数组
  14.      * @return 无
  15.      */
  16.     static void compute_prefix(const char *pattern, int next[]) {
  17.         int i;
  18.         int j = -1;
  19.         const int m = strlen(pattern);
  21.         next[0] = j;
  22.         for (i = 1; i < m; i++) {
  23.             while (j > -1 && pattern[j + 1] != pattern[i]) j = next[j];
  25.             if (pattern[i] == pattern[j + 1]) j++;
  26.             next[i] = j;
  27.         }
  28.     }
  30.     /*
  31.      * @brief KMP算法.
  32.      *
  33.      * @param[in] text 文本
  34.      * @param[in] pattern 模式串
  35.      * @return 成功则返回第一次匹配的位置，失败则返回-1
  36.      */
  37.     static int kmp(const char *text, const char *pattern) {
  38.         int i;
  39.         int j = -1;
  40.         const int n = strlen(text);
  41.         const int m = strlen(pattern);
  42.         if (n == 0 && m == 0) return 0; /* "","" */
  43.         if (m == 0) return 0;  /* "a","" */
  44.         int *next = (int*)malloc(sizeof(int) * m);
  46.         compute_prefix(pattern, next);
  48.         for (i = 0; i < n; i++) {
  49.             while (j > -1 && pattern[j + 1] != text[i]) j = next[j];
  51.             if (text[i] == pattern[j + 1]) j++;
  52.             if (j == m - 1) {
  53.                 free(next);
  54.                 return i-j;
  55.             }
  56.         }
  58.         free(next);
  59.         return -1;
  60.     }
  61. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/string/strstr.html