## Implement strStr()

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

### Updated 201401:Analysis:

A trie can solve the problem.

(unfinished)

The code below can run without error in my computer but failed the OJ(test case: "mississippi","mississippi"), anyone can tell me what's wrong with my code???

### Code(C++):

class Solution {

public:
struct Node{
map<char, Node*> child;
char chr;
char* st;
Node(char c):chr(c){};
};
void buildTrie(char* str, Node* Trie, char* st){
if(str[0]=='\0'){
Trie->child['\0']=new Node('\0');
Trie->child['\0']->st = st;
return;
}else{
if (Trie->child.find(str[0])==Trie->child.end()){
Trie->child[str[0]]=new Node(str[0]);
}
buildTrie(str+1,Trie->child[str[0]],st);
}
}

char* search(Node* root, char* needle){
if (needle[0]=='\0'){
return root->st;
}else{
if (root->child.find(needle[0])==root->child.end()){
return NULL;
}else{
return search(root->child[needle[0]],needle+1);
}
}
}

char *strStr(char *haystack, char *needle) {
Node* Trie = new Node(' ');
Node* root = Trie;
char*tmp;
for (int i=0;i<strlen(haystack);i++){
strcpy(tmp,haystack+i);
buildTrie(tmp,Trie,haystack+i);
}
return search(root,needle);
}
};


### (KMP Algorithm)Analysis:

This is a classical string problem, which can be solved using the famous KMP problem.
Relative website:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
Another Chinese website:
http://blog.csdn.net/lin_bei/article/details/1252686

### Code(C++):

class Solution {
public:
void getnext(const char* p, int lp, vector<int>& next)
{
next[0] = -1;
int i = 0;
while(i < lp - 1)
{
int idx = i >= 0? next[i]: -1;
if(-1 == idx)
next[++i] = ++idx;
else if(p[i] == p[idx])
next[++i] = ++idx;
else
{
while(idx >= 0 && p[i] != p[idx])
idx = next[idx];
next[++i] = ++idx;
}
}
}
int match(char* s, char* p, int ls, int lp)
{
vector<int> next(lp);
int i = 0;
int j = 0;
getnext(p, lp, next);
while(i < strlen(s))
{
if(-1 == j || s[i] == p[j])
{
++i;
++j;
}
else
j = next[j];
if(j == lp)
return i - lp;
}
return -1;
}

char *strStr(char *haystack, char *needle) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int l_need = strlen(needle);
if(l_need == 0) return haystack;
int l_hay = strlen(haystack);
if(l_hay == 0)    return NULL;

int idx = match(haystack, needle, l_hay, l_need);
if(idx >= 0)
return haystack+idx;

return NULL;
}
};


### KMP Code (Python):

class Solution:
# @param haystack, a string
# @param needle, a string
# @return an integer

def computeLps(self, needle):
lps = [0] * len(needle)
lon = 0
i = 1
while i < len(needle):
if needle[lon] == needle[i]:
lon += 1
lps[i] = lon
i += 1
else:
if lon == 0:
lps[i] = 0
i += 1
else:
lon = lps[lon-1]
return lps

def strStr(self, haystack, needle):
if needle == "":
return 0

lps = self.computeLps(needle)
i = 0
j = 0

while i<len(haystack):
if haystack[i] == needle[j]:
i += 1
j += 1

if j == len(needle):
return i-j
elif i< len(haystack) and haystack[i]!=needle[j]:
if j==0:
i += 1
else:
j = lps[j-1]
return -1



#### 1 comment:

1. /* Not Boyer/Moore Not KMP. Minimal. But for many situations reasonable. */
char *strstr(const char *s1, const char *s2) {
const char *a = s1, *b = s2;
for (;;)
if (!*b) return (char *)s1;
else if (!*a) return NULL;
else if (*a++ != *b++) {a = ++s1; b = s2;}
}