[LeetCode]Implement strStr()

可以用Rolling Hash解，但是要考虑conflicts的情况。KMP的解法请参考这篇文章。代码如下：

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	int lenH = haystack.size(), lenN = needle.size();
	if(lenH < lenN)return -1;
	//KMP, calculate next array
	vector<int> next(lenN + 1, -1);
	int k = -1, i = 0;
	while(i < lenN)
	{
	if(k == -1 || needle[i] == needle[k])
	next[++i] = ++k;
	else
	k = next[k];
	}
	int j = 0;
	i = 0;
	while(i < lenH && j < lenN)
	{
	if(j == -1 || haystack[i] == needle[j])
	{
	++i;
	++j;
	}
	else
	j = next[j];
	}
	return j == lenN? i - lenN: -1;
	}
	};

view raw Implement strStr()_I.cpp hosted with ❤ by GitHub

优化KMP如下：

	class Solution {
	public:
	int strStr(string haystack, string needle) {
	int lenH = haystack.size(), lenN = needle.size();
	if(lenH < lenN)return -1;
	//KMP, calculate next array
	vector<int> next(lenN + 1, -1);
	int k = -1, i = 0;
	while(i < lenN)
	{
	if(k == -1 || needle[i] == needle[k])
	{
	++i;
	++k;
	if(needle[i] == needle[k])
	next[i] = next[k];
	else
	next[i] = k;
	}
	else
	k = next[k];
	}
	int j = 0;
	i = 0;
	while(i < lenH && j < lenN)
	{
	if(j == -1 || haystack[i] == needle[j])
	{
	++i;
	++j;
	}
	else
	j = next[j];
	}
	return j == lenN? i - lenN: -1;
	}
	};

view raw Implement strStr()_II.cpp hosted with ❤ by GitHub