字符串|28. 实现 strStr() 、459.重复的子字符串

28. 实现 strStr()

自己审题思路

这道题刚开始只能想到暴力解法

代码（暴力解法1）：

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; i++) {
            bool flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack[i + j] != needle[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
};

代码（暴力解法2）：

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        for(int i = 0; i <= n - m; i++){
            int j = i, k = 0; 
            while(k < m && s[j] == p[k]){
                j++;
                k++;
            }
            if(k == m) return i;
        }
        return -1;
    }
};

看完代码随想录题解后的收获

了解了KMP算法，难点在于next数组的建立。将next数组的建立理解为前缀和后缀的匹配过程，next数组的构建的代码会好些出来一些。

代码（自己完成）：

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

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

            match = i - j;
            while (needle[j] == haystack[i]) {
                j++;
                i++;
                if (j == needle.size()) return match;
            }
        }
        return -1;
    }
};

next直接用数组就好

代码（代码随想录）

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

参考详解

459.重复的子字符串

自己审题思路

暴力解法，一个for循环用来选取子串，一个for循环用子串拼接字符串

代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
    if(s.size()==1) return false;
    string temp="",str="";
    for(int i=0;i<s.size()/2;++i)
    {
        temp+=s[i];
        while(str.size()<=s.size())
        {
            str+=temp;
            if(str.compare(s)==0)
            {
               return true;
            }
        }
        str="";
    }
    return false;
    }
};

看完代码随想录题解后的收获

1、 移动匹配
判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。
2、KMP
在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串

代码（移动匹配）

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
    if(s.size()==1) return false;
    string temp="",str="";
    for(int i=0;i<s.size()/2;++i)
    {
        temp+=s[i];
        while(str.size()<=s.size())
        {
            str+=temp;
            if(str.compare(s)==0)
            {
               return true;
            }
        }
        str="";
    }
    return false;
    }
};

代码（KMP）

class Solution {
public:
    void getNext (int* next, const string& s){
        next[0] = 0;
        int j = 0;
        for(int i = 1;i < s.size(); i++){
            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;
        }
        int next[s.size()];
        getNext(next, s);
        int len = s.size();
        if (next[len - 1] != 0 && len % (len - (next[len - 1] )) == 0) {
            return true;
        }
        return false;
    }
};

参考详解

今日感悟

KMP算法next数组的求解涉及到动态规划，理解了这点KMP算法就比较好写了。