题目链接

题目描述

实现 strStr() 函数。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

示例

示例1：

输入：haystack = “hello”, needle = “ll” 输出：2

提示

  • 0 <= haystack.length, needle.length <= 5 * 10

  • haystack 和 needle 仅由小写英文字符组成

    思路

    KMP算法

    1. class Solution {
    2.  private:
    3.   void getNext(int* next, const string& t) {
    4.       int j = 0;
    5.       next[0] = 0;
    6.       for (int i = 1; i < (int)t.size(); ++i) {
    7.           while (j > 0 && t[i] != t[j]) {
    8.               j = next[j - 1];
    9.           }
    10.           if (t[i] == t[j]) {
    11.               ++j;
    12.           }
    13.           next[i] = j;
    14.       }
    15.   }
    17.  public:
    18.   int strStr(string haystack, string needle) {
    19.       if (needle.size() == 0) {
    20.           return 0;
    21.       }
    22.       int* next = new int[needle.size()];
    23.       getNext(next, needle);
    24.       int j = 0;
    25.       for (int i = 0; i < (int)haystack.size(); ++i) {
    26.           while (j > 0 && haystack[i] != needle[j]) {
    27.               j = next[j - 1];
    28.           }
    29.           if (haystack[i] == needle[j]) {
    30.               ++j;
    31.           }
    32.           if (j == needle.size()) {
    33.               delete[] next;
    34.               next = nullptr;
    35.               return (i - needle.size() + 1);
    36.           }
    37.       }
    38.       delete[] next;
    39.       next = nullptr;
    40.       return -1;
    41.   }
    42. };

    题解

    复杂度分析

  • 时间复杂度：0028-实现strStr() - 图1

  • 空间复杂度：0028-实现strStr() - 图2