题目描述

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

样例

示例 1:

输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:

输入: haystack = "aaaaa", needle = "bba"
输出: -1

算法1

(KMP) $O(n + m)$

KMP模板来一发。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        int i = 0, j = 0;
        vector<int> next = getNext(p);

        while (i < n && j < m){
            if (j < 0 || s[i] == p[j]) ++i, ++j;
            else j = next[j];
        }

        return j < m ? -1 : i - j;
    }

    vector<int> getNext(string &p){
        if (p.empty()) return {};

        int m = p.size();
        vector<int> next(m); next[0] = -1;
        int t = -1, j = 0;

        while (j < m - 1){
            if (t < 0 || p[j] == p[t]){
                ++j; ++t; 
                next[j] = p[j] == p[t] ? next[t] : t;
            }
            else t = next[t];
        }

        return next;
    }
};