Leetcode 28. 实现 strStr()（DAY 141） ---- LeetCode 精选 TOP 面试题

小咪咪 2022-08-29 10:54 198阅读 0赞

### 文章目录 ###

*   *  原题题目
     *  代码实现（首刷自解）

--------------------

## 原题题目 ##

--------------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]

--------------------

## 代码实现（首刷自解） ##

--------------------

class Solution { 
    public:
        void getnext(string& str,vector<int>& next)
        { 
            int i = 0; 
            for(int j=1;j<next.size();++j)
            { 
                while(str[i] != str[j] && i > 0)    i = next[i-1];
                if(str[i] == str[j])
                { 
                    next[j] = ++i;
                }
                else    next[j] = 0;
            }
            for(int i=next.size()-1;i>=1;--i)
                next[i] = next[i-1];
        }
    
        int strStr(string haystack, string needle) { 
            if(needle == "")    return 0;
            vector<int> next(needle.size(),0);
            getnext(needle,next);
            next[0] = -1;
            int pos1 = 0,pos2 = 0;
            for(int pos1=0;pos1<haystack.size();)
            { 
                if(haystack[pos1] == needle[pos2])
                { 
                    ++pos2;
                    ++pos1;
                    if(pos2 == needle.size())   return pos1-needle.size();
                }
                else
                { 
                    while(pos2 != -1 && haystack[pos1] != needle[pos2])
                        pos2 = next[pos2];
                    if(pos2 == -1)  ++pos2,++pos1;
                }
            }
            return -1;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTAwNTE2_size_16_color_FFFFFF_t_70]: /images/20220829/193e7a3d2dce42adb563c168de3d0b60.png