LeetCode_28: Implement strStr()

# 引言

题目链接：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
}