LeetCode_28: Implement strStr() - LeetCode

# 引言

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

实现 strStr()

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

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

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

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

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

时间复杂度 O(n+m)

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

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
	}