引言

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

459. 重复的子字符串 - 力扣（LeetCode）

20. 有效的括号 - 力扣（LeetCode）

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）

第一题

这一题是KMP的经典题目

首先KMP最重要的就是next数组的求解，我觉得其中最难理解的就是回跳的这一个过程。i是遍历整个数组的，所以我们不可能调动i，j是操作最长前缀的，所以我们调动的是j。因为求的是最长相等的前缀和后缀，所以对于我们需要跳到前一个数，看一看前一个数的next数组里面是啥，然后跳到对应数组的位置，这个位置就是以前面一个数为结尾的最短前缀，这个并不是我们想要的结果，因为这个结果我们已经验证过了，不匹配，但是因为我们next数组设置数据的特别，前缀是从0开始的，所以我们正好可以跳到前面一个的数，完全不用担心我们正好跳到的位置是以前面一个数为结尾的最短前缀。（换一句话说就是最长前缀里面也有最长前缀，我们需要跳到前缀里面的前缀）

当我们拿到这个next数组之后，记得是对needle求next数组，如果不符合，那么就开始回跳。回跳的过程和next数组求解的过程一模一样，因为也是找和当前位置最长的前后缀。

不过总的来说，有一个细节需要注意，回跳和相等++是并列存在的，也就是说不可以写成else。既然是这样，那会跳的过程，也就是while（）循环的过程必须写在前面，++写在后面

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0; 
        next[0] = 0;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] != s[j]) {
                while (j > 0 && s[i] != s[j]) {
                    j = next[j - 1];
                }
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j; 
        }
    }

    int strStr(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;
        }
        vector<int> next(needle.size());
        getNext(&next[0], needle);
        int j = 0;
        for(int i = 0;i < haystack.size(); i++) {
            if (needle[j] != haystack[i]) {
                while (j > 0 && haystack[i] != needle[j]) {
                    j = next[j - 1];
                }  
            }
            if (needle[j] == haystack[i]) {
                j++;
            }
            if (j == needle.size()) {
                return i - j + 1;
            }
        }
        return -1;
    }
};

第二题

这一题也是KMP的经典题目，总的来说就是判断一个字符串是不是由某个相同的字串不停重复形成的。那么这一题为什么使用KMP呢。因为KMP的一个很重要的思想就是最长前后缀，比如有一个abababab，那么对于这个是由相同字符串组成的最长字符串，它的最长前后缀一定是相同的，第一个ab最为开始的模板，在next数组里面都是0，而后面的所有字母都是与前面进行的匹配，如果这个是重复的字符串，那么后面的字符串就会不停的被匹配，比如这个字符串，2和0匹配，4和2匹配，那相当于是4和0匹配，所以最后匹配完之后，得到的那个最长的后缀，其实就是不包含刚开始的模板ab，而这个ab也就是我们要求的那个最小重复子串。但是我们最后是对这个len - next[len - 1])) == 0判断，因为我们不知道这个重复子串出现了几次，可能是一次，还是很多次。

class Solution {
public:
    void getNext(int *next, const string& s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.size(); i++) {
            if (s[i] != s[j]) {
                while (j > 0 && s[i] != s[j]) {
                    j = next[j - 1];
                }
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        if (s.size() == 0) {
            return false;
        }
        vector<int> next(s.size());
        getNext(&next[0], s);
        int len = s.size();
        if (next[len - 1] != 0 && (len % (len - next[len - 1])) == 0) {
            return true;
        } else {
            return false;
        }
    }
};

第三题

这一题我们必须要先思考好我们的解题思路，否则会在写代码的时候非常乱。我们的思路就是遇到正的括号就把反括号加入进去，然后遇到反括号的时候，看一看这个反括号与栈顶的元素是不是相同的，如果是相同的就删除栈顶元素，代表的是匹配成功，否则直接返回false。到最后判断这个栈是不是空的，如果不是空的，说明有的元素没有被成功匹配，返回false。

class Solution {
public:
    bool isValid(string s) {
        if (s.size() % 2 != 0) {
            return false;
        }
        stack<char> st;
        for(int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                st.push(')');
            } else if (s[i] == '{') {
                st.push('}');
            } else if (s[i] == '[') {
                st.push(']');
            } else if (st.empty() || st.top() != s[i]) {
                return false;
            } else {
                st.pop();
            }
        }
        return st.empty();
    }
};

第四题

对于删除相邻的数据，栈可以起到很好的作用，因为栈可以存储当前元素的上一个元素，而当我们删除了栈顶的元素之后，下一个栈顶的元素是上上个元素，所以栈是一个很好记录遍历过元素的一容器。

class Solution {
public:
    string removeDuplicates(string s) {
        stack<char> st;
        for(int i = 0; i < s.size(); i++) {
            if(!st.empty() && st.top() == s[i]) {
                st.pop();
            } else {
                st.push(s[i]);
            }
        }
        string res;
        res.resize(st.size());
        for(int i = st.size() - 1; i >= 0; i--) {
            res[i] = st.top();
            st.pop();
        }
        return res;
    }
};

总结

对于KMP的next数组求解，每个人都有每个人的理解和求法，掌握自己的那一种方法就可以。但是不是只需要写出代码那么简单，就像第二题，我们需要真正理解KMPnext数组的含义，才可以把这个方法移动到其他地方。

本篇文章就到这里结束了！！！希望可以帮助大家理解~~~