# 引言

题目链接:https://leetcode.com/problems/implement-strstr/

# 题目大意

实现 strStr()

返回 haystack 中第一次出现模式串的索引,如果模式串不是 haystack 的一部分,则返回 - 1。

Hint: 当模式串为空的时候,返回 0 (没看到这个居然被坑了 T_T)

  • Example
Input: haystack = "hello", needle = "ll"
Output: 2

Input: haystack = "aaaaa", needle = "bba"
Output: -1

# 题解

# 一句话题解

KMP 算法,关于 KMP 算法推荐一篇感觉讲的很有灵魂的博客!Click Here!

# 复杂度

时间复杂度 O(n+m)

空间复杂度 O(m) , m 代表模式串 (需要匹配的字符串) 的长度

# AC 代码

c++ 版本

class Solution
{
  public:
    int strStr(string haystack, string needle)
    {
        int len = needle.length();
        if (len <= 0)
        {
            return 0;
        }
        int *next = getNext(needle);
        int ret = -1;
        for (int i = 0, j = 0; i < haystack.length(); ++i)
        {
            while (j > 0 && haystack[i] != needle[j])
            {
                j = next[j];
            }
            if (haystack[i] == needle[j])
            {
                ++j;
            }
            if (j == len)
            {
                ret = i - j + 1;
                break;
            }
        }
        delete[] next;
        return ret;
    }
  private:
    int *getNext(const string &needle)
    {
        int *next = new int[needle.length() + 1];
        next[0] = next[1] = 0;
        for (int i = 1, j = 0; i < needle.length(); ++i)
        {
            while (j > 0 && needle[j] != needle[i])
            {
                j = next[j];
            }
            next[i + 1] = needle[j] == needle[i] ? ++j : j;
        }
        return next;
    }
};

go 版本

func getNext(needle string) []int {
	lens := len(needle)
	next := make([]int, lens+1)
	for i, j := 1, 0; i < lens; i++ {
		for j > 0 && needle[j] != needle[i] {
			j = next[j]
		}
		if needle[i] == needle[j] {
			j++
		}
		next[i+1] = j
	}
	return next
}
func strStr(haystack string, needle string) int {
	len1 := len(needle)
	if len1 <= 0 {
		return 0
	}
	ret, next, len2 := -1, getNext(needle), len(haystack)
	for i, j := 0, 0; i < len2; i++ {
		for j > 0 && haystack[i] != needle[j] {
			j = next[j]
		}
		if haystack[i] == needle[j] {
			j++
		}
		if j == len1 {
			ret = i - j + 1
			break
		}
	}
	return ret
}
更新于 阅读次数

请我喝[茶]~( ̄▽ ̄)~*

yx.zhang 微信支付

微信支付

yx.zhang 支付宝

支付宝