leetcode 28. Implement strStr() (easy)

1. 暴力破解

class Solution
{
    
public:int strStr(const string &haystack, const string &needle){
    if (needle.empty())return 0;const int N = haystack.size() - needle.size() + 1;for (int i = 0; i < N; i++){
    int j = i;int k = 0;while (j < haystack.size() && k < needle.size() && haystack[j] == needle[k]){
    j++;k++;}if (k == needle.size())return i;}return -1;}
};

2. KMP算法

class Solution
{
    
private:vector<int> getnext(const string &str){
    vector<int> next(str.length(), 0);next[0] = -1;int j;int k = -1;for (j = 1; j < str.length(); ++j){
    while (k > -1 && str[k + 1] != str[j])k = next[k];if (str[j] == str[k + 1])++k;next[j] = k;}return next;}public:int strStr(const string &text, const string &pat){
    if (pat.empty())return 0;vector<int> next = getnext(pat);for (int i = 0, j = -1; i < text.length(); i++){
    while (j > -1 && pat[j + 1] != text[i])j = next[j];if (text[i] == pat[j + 1])++j;if (j == pat.length() - 1)return i - j;}return -1;}
};