leetcode Question 34: Implement strStr()

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