首页 > 代码库 > 【LeetCode】Implement strStr()

【LeetCode】Implement strStr()

2024-07-06 04:11:21   227人阅读

 

Implement strStr()

Implement strStr().

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

 

标准KMP算法。可参考下文。

http://blog.csdn.net/yaochunnian/article/details/7059486

核心思想在于求出模式串前缀与后缀中重复部分，将重复信息保存在next数组中。

class Solution 
{
public:
    int getlen(char *str)
    {
        int i;
        for(i = 0; str[i] != ‘\0‘; i ++)
            ;
        return i;
    }
    void getnext(char *str, int len, int next[])
    {
        int i = 0;
        next[i] = -1;
        int j = -1;

        while(i < len-1)
        {
            if(j==-1 || str[i]==str[j])
            {
                i++;
                j++;
                if(str[i] == str[j])
                    next[i] = next[j];
                else
                    next[i] = j;
            }
            else
                j = next[j];
        }
    }

    char *strStr(char *haystack, char *needle) 
    {
        int hlen = getlen(haystack);
        //cout << "hlen:" << hlen << endl;
        int nlen = getlen(needle);
        //cout << "nlen:" << nlen << endl;

        int *next = new int[nlen];
        getnext(needle, nlen, next);


        int i = 0;
        int j = 0;
        while(i != hlen && j != nlen)
        {
            if(j == -1 || haystack[i] == needle[j])
            {
                i++;
                j++;
            }
            else
            {
                j = next[j];
            }
        }
        if(j == nlen)
            return &haystack[i-nlen];
        else
            return NULL;
    }
};


联系
我们