leetcode第27题--Implement strStr()

Implement strStr().

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

就是判断haystack中是否有needle，如果包含的话，返回第一次包含的地址。如果没有则返回NULL。

这题官网打出来的是easy，但是要做好绝不简单。我能想到的就是O(m*n)的复杂度了。最经典的是用KMP算法。

class Solution {

public:
    char *strStr(char *haystack, char *needle) 
    {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int lena = strlen(haystack);
        int lenb = strlen(needle);
        if(lena < lenb)
            return NULL;
        if(lena == lenb)
        {
            if(strcmp(haystack, needle)==0)
                return haystack;
            return NULL;
        }
        for(int i=0; i<=lena-lenb; i++)
        {
            bool flag = true;
            for(int j=0; j<lenb; j++)
            {
                if(haystack[i+j] != needle[j])
                {
                    flag = false;
                    break;
                }
            }
            if(flag)
                return haystack + i;
        }
        return NULL;
    }
};