LeetCode OJ--Implement strStr()

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

判断一个串是否为另一个串的子串

比较简单的方法，复杂度为O(m*n),另外还可以用KMP时间复杂度为O(m+n)，之前面试的时候遇到过。

class Solution {
public:
    bool isEqual(char *a,char *b)
    {
        char* chPointer = a;
        char* chPointer2 = b;
        while(*chPointer2!= '' && *chPointer!='' )
        {
            if(*chPointer == *chPointer2)
            {
                chPointer++;
                chPointer2++;
            }
            else
                return false;
        }
        return true;
    }
    char *strStr(char *haystack, char *needle) {
        char* chPointer = haystack;
        char* chPointer2 = needle;
        if(haystack == NULL || needle ==NULL || haystack =="")
            return NULL;
        while(chPointer)
        {
            if(isEqual(chPointer,needle))
                return chPointer;
            chPointer++;
        }
        return NULL;
    }
};

class Solution {
public:
    void compute_prefix(const char* pattern,int next[])
    {
        int i;
        int j = -1;
        const int m = strlen(pattern);
        next[0] = j;
        for(i =1;i<m;i++)
        {
            while(j>-1 && pattern[j+1] != pattern[i]) j = next[j];
            if(pattern[i]== pattern[j+1])
                j++;
            next[i] = j;
        }
    }
    int kmp(const char* text , const char* pattern)
    {
        int i;
        int j = -1;
        const int n = strlen(text);
        const int m = strlen(pattern);
        if(n == m && m==0)
            return 0;
        if(m == 0)
            return 0;
        int *next = (int *)malloc(sizeof(int) * m);
        
        compute_prefix(pattern, next);

        for(i = 0;i <n;i++)
        {
            while(j >-1 && pattern[j+1] != text[i])
                j = next[j];
            if(text[i] == pattern[j+1]) j++;
            if(j==m-1)
            {
                free(next);
                return i-j;
            }
        }
    }
    char *strStr(char *haystack, char *needle) {
       int position = kmp(haystack,needle);
       if(position == -1)
           return NULL;
       else
           return (char*)haystack + position;
    }
};