The problem is:

Implement strStr().

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

A naive method: (1) find the the first letter of needle in haystack, (2)comparing other consecutive characters of needle and haystack, (3) if all letters in needle can be found in haystack consecutively, then return the position in haystack.

class Solution {
public:
char *strStr(char *haystack, char *needle) {
if(haystack==NULL || needle==NULL)
return NULL;

if(needle[0]=='\0')
return haystack;

// Find the first character of needle in haystack
int hay_len=strlen(haystack);
int need_len=strlen(needle);
int pos=0;
bool found=false;
while(hay_len-pos>=need_len && haystack[pos]!='\0') {
if(haystack[pos] == needle[0]){
int th=pos+1;
int tn=1;
while(haystack[th] == needle[tn]) {
if(needle[tn]=='\0')
break;
th++;
tn++;
}
if(tn == need_len) {
found=true;
break;
}
}
pos++;
}

if(found)
return haystack+pos;
else
return NULL;
}
};


A better solution is to use the famous KMP algorithm(http://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/).

class Solution {
public:
char *strStr(char *haystack, char *needle) {
if(haystack==NULL || needle==NULL)
return NULL;
if(needle[0]=='\0')
return haystack;

int n=strlen(haystack);
int m=strlen(needle);
vector<int> pi(m); // the longest proper prefix which is also suffix
computePrefix(needle,pi);
//printPrefix(pi); // TEST ONLY

int q=0; // index for needle
int i=0; // index for haystack
while(i<n) {
//cout<<"needle["<<q<<"]="<<needle[q]<<", haystack["<<i<<"]="<<haystack[i]<<endl; // TEST ONLY
if(needle[q]==haystack[i]) {
q++;
i++;
}
if(q==m) {
//cout<<"Pattern occurs with shift "<<i-m<<endl; // TEST ONLY
return haystack+i-m;
} else if(needle[q]!=haystack[i]) {
if(q!=0)
q=pi[q-1];
else
i++;
}
}
return NULL;
}

// Calculate the longest proper prefix which is also suffix.
// Examples:
// 	For the pattern “AABAACAABAA”, lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
//	For the pattern “ABCDE”, lps[] is [0, 0, 0, 0, 0]
//	For the pattern “AAAAA”, lps[] is [0, 1, 2, 3, 4]
//	For the pattern “AAABAAA”, lps[] is [0, 1, 2, 0, 1, 2, 3]
//	For the pattern “AAACAAAAAC”, lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
void computePrefix(char* P, vector<int>& pi) {
int m=strlen(P);
pi[0]=0; // lps[0] is always 0
int k=0; // length of the previous prefix suffix
int i=1;
while(i<m) {
if(P[k]==P[i]) {
k++;
pi[i]=k;
i++;
} else {
if(k!=0) {
k=pi[k-1];
} else {
pi[i]=0;
i++;
}
}
}
}

void printPrefix(vector<int>& pi) {
cout<<"pi={ ";
for(auto& x:pi)
cout<<x<<" ";
cout<<"}"<<endl;
}
};