leetcode--Implement strStr()

1.题目描述

Implement strStr().

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

2.解法分析

KMP算法的一个应用而已，KMP算法见我的另一篇文章，以下是KMP算法应用在这个题目中。

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(needle==NULL)return needle;
        if(needle[0]=='')return haystack;

        int i=0;int j=0;
        vector<int>p=prepressing(needle);
        int len=p.size();

        while(haystack[i]!='')
        {
            if(j==len)
            {
                return &haystack[i-len];
            }

            if(haystack[i]==needle[j])
            {
                i++;j++;
            }
            else
            {
                while(j!=0&&needle[j]!=haystack[i])j=p[j-1];

                if(j==0&&needle[j]!=haystack[i])i++;
            }
        }

        if(j==len)
        {
            return &haystack[i-len];
        }
        return NULL;


    }

    vector<int> prepressing(char *needle)
    {
        //ret[i]存放的是needle的前i+1个字符能再次利用的长度
        vector<int> ret;
        ret.push_back(0);
        int i=1;
        while(needle[i]!='')
        {
            ret.push_back(0);
            int j=ret[i-1];
            while(needle[i]!=needle[j]&&j!=0)
            {
                j=ret[j-1];
            }

            if(needle[i]==needle[j])j++;

            ret[i]=j;
            i++;
        }

        return ret;
    }
};