http://oj.leetcode.com/problems/implement-strstr/

Implement strStr() .cpp

class Solution {
public:
	char *strStr(char *haystack, char *needle) {
	    if (!haystack || !needle) return NULL;
		int N=strlen(needle);
		if (N<1) (haystack[0]=='\0') ? haystack : NULL;
		
		int *next=new int[N];
		computeNext(needle, next, N);
		char *p=haystack; int j=0;
		while (*p && j<N) {
			if (j==-1 || *p==needle[j]) ++p, ++j;
			else j=next[j];
		}
		delete [] next;
		if (j<N) return NULL;
		return p-N;
	}
	void computeNext(char *pat, int next[], int N) {
		next[0]=-1; int i=1, j=-1;
		while (i<N) {
			if (j==-1 || pat[i-1]==pat[j]) next[i++]=++j;
			else j=next[j];
		}
	}
};

KMP algorithm.