LeetCode 28. 实现 strStr()

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

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

说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当 needle 是空字符串时我们应当返回 0 。
这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size() == 0)
        	return 0;
        int i = 0, j = 0, i0;
        for(i = 0; i < haystack.size(); ++i)
        {
        	for(i0 = i,j = 0; i0 < haystack.size() && j < needle.size(); ++j)
        	{
        		if(haystack[i0] == needle[j])
        		{
        			++i0;
        			if(j == needle.size() -1)
        				return i;
                }
        		else
        			break;
        	}
        }
        return -1;
    }
};

class Solution {
public:
    int strStr(string s, string p) {
        return kmp(s, p);
    }
    int kmp(string& s, string& p){
        int n1 = s.size(), n2 = p.size();
        vector<int> next(n2+1);
        calnext(p, next);
        int i = 0, j = 0;
        while(i < n1 && j < n2)
        {
            if(j == -1 || s[i] == p[j])
            {
                i++,j++;
            }
            else
                j = next[j];
        }
        if(j == n2)
            return i-j;
        return -1;
    }
    void calnext(string& p, vector<int>& next){
        int i = 0, j = -1;
        next[0] = -1;
        while(i < p.size())
        {
            if(j == -1 || p[i] == p[j])
            {
                i++,j++;
                next[i] = j;
            }
            else
                j = next[j];
        }
    }
};