简单的字符串匹配

方法一、暴力匹配

needle 与 haystack 的所有长度为 m 的字符串均匹配一次。每次匹配失败就立刻停止当前的匹配，继续对下一个字符串匹配，当前字符串匹配成功，返回当前开始位置，所有均失败返回 -1 ；

  1. int strStr(char* haystack, char* needle) {
  2.     int n = strlen(haystack), m = strlen(needle);
  3.     for (int i = 0; i + m <= n; i++) {
  4.         bool flag = true;
  5.         for (int j = 0; j < m; j++) {
  6.             if (haystack[i + j] != needle[j]) {
  7.                 flag = false;
  8.                 break;
  9.             }
  10.         }
  11.         if (flag) {
  12.             return i;
  13.         }
  14.     }
  15.     return -1;
  16. }
  1. class Solution {
  2. public:
  3.     int strStr(string haystack, string needle) {
  4.         int n = haystack.size(), m = needle.size();
  5.         for (int i = 0; i + m <= n; i++) {
  6.             bool flag = true;
  7.             for (int j = 0; j < m; j++) {
  8.                 if (haystack[i + j] != needle[j]) {
  9.                     flag = false;
  10.                     break;
  11.                 }
  12.             }
  13.             if(flag) {
  14.                 return i;
  15.             }
  16.         }
  17.         return i;
  18.     }
  19. }

时间复杂度：O(n x m);
空间复杂度：O(1);

Knuth-Morris-Pratt 算法

KMP 算法

思想：（待补充）

  1. int strStr(char* haystack, char* needle) {
  2.     int n = strlen(haystack), m = strlen(needle);
  3.     if (m == 0) {
  4.         return 0;
  5.     }
  6.     int pi[m];
  7.     pi[0] = 0;
  8.     for (int i = 1, j = 0; i < m; i++) {
  9.         while (j > 0 && needle[i] != neeldle[j]) {
  10.             j = pi[j - 1];
  11.         }
  12.         if (needle[i] == needle[j]) {
  13.             j++;
  14.         }
  15.         pi[i] = j;
  16.     }
  17.     for (int i = 0, j = 0; i < n; i++) {
  18.         while (j > 0 && haystack[i] != needle[j]) {
  19.             j = pi[j - 1];
  20.         }
  21.         if (haystack[i] == needle[j]) {
  22.             j++;
  23.         }
  24.         if (j == m) {
  25.             return i - m + 1; 
  26.         }
  27.     }
  28.     return -1;
  29. }
  1. class Solution {
  2. public:
  3.    int strStr(string haystack, string needle) {
  4.        int n = haystack.size(), m = needle.size();
  5.        if (mm == 0) {
  6.            return 0;
  7.        }
  8.        vector<int> pi[m];
  9.        for (int i = 1, j = 0; i < m; i++) {
  10.            while (j > 0 && needle[i] != needle[j]) {
  11.               j = pi[j - 1]; 
  12.            }
  13.            if (needle[i] == needle[j]) {
  14.                j++;
  15.            }
  16.            pi[i] = j;
  17.        }
  18.        for (int i = 0, j = 0; i < n; i++) {
  19.            while (j > 0 && haystack[i] != needle[j]) {
  20.                j = pi[j - 1];
  21.            }
  22.            if (haystack[i] == needle[j]) {
  23.                j++;
  24.            }
  25.            if (j == m) {
  26.                return i - m + 1;
  27.            }
  28.        }
  29.        return -1;
  30.    }
  31. }

复杂度

  • 时间复杂度：O(n + m)
  • 空间复杂度：O(m)

LC实现 strStr() 题解