LeetCode——实现 strStr()【KMP算法实现】

写在前面的话：不知道为啥LeetCode会分类到简单题，深坑题。网上KMP算法代码在LeetCode存在各种问题，dubug了两天。

在理论层面分为两种KMP算法：

①string[0]为字符串长度——《大话数据结构》

②string[0]为第一个元素——本文代码

void makeNext(string P, long next[])
{
    next[0] = 0;
    for (int i = 0, j = 0; i < P.size(); i++)
    {
	    next[i] = j;
	    while (j > 0 & P[i] != P[j])
		    j = next[j];
	    if (P[i] == P[j] & i != 0)
		    j++;
    }
}
int strStr(string haystack, string needle) 
{
    if (haystack.size() < needle.size())
        return -1;
    if (needle.size() == 0)
        return 0;
    long next[65535] = { 0 };
    int len_hay = haystack.size();
    int len_nee = needle.size();
    makeNext(needle, next);
    int i = 0, j = 0;
    for (; i < len_hay & j < len_nee; ++i)
    {
        while(j > 0 & haystack[i] != needle[j])
            j = next[j];
        if (haystack[i] == needle[j])
        {
            ++j;
        }
    }
    if (j == len_nee)
        return i - j;
    return -1;
}

普通算法【字符逐个比较】

int strStr(string haystack, string needle) {
	if (haystack.size() < needle.size())
		return -1;
	if (needle.size() == 0 | haystack == needle)
		return 0;
	int len_hay = haystack.size();
	int len_nee = needle.size();
	for (unsigned i = 0; i < haystack.size() - len_nee + 1; i++)
	{
		if(haystack.substr(i,len_nee) == needle)
            return i;    
    }
    return -1;
}