【LeetCode】28. Implement strStr()

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

题目大意：实现一个子串查找函数

题目链接：https://leetcode.com/problems/implement-strstr/description/

这个查找方法，除了最简单的，应该就Kmp比较出名了。

这里没办法讲这个题，主要就是Kmp算法的应用。

C++代码如下:

class Solution {
public:
    vector<int> kmpPrev(string x)
    {
        //计算得出next数组
        vector<int> next(x.size()+1, -1);
        int i = 0;
        int j = next[0] = -1;
        while(i < x.size())
        {
            while(-1 != j && x[i] != x[j])
            {
                j = next[j];
            }
            next[++i] = ++j;
        }
        return next;
    }
    
    int Kmp(string x, string y)
    {
         //x是模式串, y是主串, 模式串为空的情况下, 返回0
        if(x.empty())
        {
            return 0;
        }

        int i = 0;
        int j = 0;
        vector<int> next = kmpPrev(x);
        while(i < y.size())
        {
            while(-1 != j && y[i] != x[j])
            {
                j = next[j];
            }
            i++;
            j++;
            if(j >= x.size())
            {
                //主串的匹配完毕位置, 减去模式串的长度
                return i - x.size();
            }
        }
        //没找到返回-1
        return -1;
    }
    
    int strStr(string haystack, string needle) {
        return Kmp(needle, haystack);
    }
};

class Solution {

public:

vector<int> kmpPrev(string x)

{

//计算得出next数组

vector<int> next(x.size()+1, -1);

int i = 0;

int j = next[0] = -1;

while(i < x.size())

{

while(-1 != j && x[i] != x[j])

{

j = next[j];

}

next[++i] = ++j;

}

return next;

}

int Kmp(string x, string y)

{

//x是模式串, y是主串, 模式串为空的情况下, 返回0

if(x.empty())

{

return 0;

}

int i = 0;

int j = 0;

vector<int> next = kmpPrev(x);

while(i < y.size())

{

while(-1 != j && y[i] != x[j])

{

j = next[j];

}

i++;

j++;

if(j >= x.size())

{

//主串的匹配完毕位置, 减去模式串的长度

return i - x.size();

}

//没找到返回-1

return -1;

}

int strStr(string haystack, string needle) {

return Kmp(needle, haystack);

}

};

大致如此。

【LeetCode】28. Implement strStr()

Tagged on: C++ LeetCode