leetcode 刷題之路 48 Implement strStr()

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

字元串比對。

這裡給出KMP算法的實作，還可以用BF，BM算法等。

class Solution {
public:
	char *strStr(char *haystack, char *needle)
	{
		if (haystack == NULL || needle == NULL)
			return NULL;
		int len1 = strlen(needle);
		int len2 = strlen(haystack);
		if (len1 == 0)
			return haystack;
		int *next = new int[len1];
		getNext(next, needle);
		int i = 0, j = 0;
		while (i<len2&&j<len1)
		{
			if (j == -1 || haystack[i] == needle[j])
			{
				j++;
				i++;
			}
			else
			{
				j = next[j];
			}
			if (j == len1)
				return &(haystack[i - len1]);
		}
		return NULL;
	}
	void getNext(int *next, const char* needle)
	{
		int i = 0, k = -1;
		next[0] = -1;
		int len = strlen(needle);
		while (i<len-1)
		{
			if (k == -1 || needle[i] == needle[k])
			{
				if (needle[++k] == needle[++i])
					next[i] = next[k];
				else
					next[i] = k;
			}
			else
				k = next[k];
		}
	}
};