day18

【0459.重复的子字符串】

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        for (int i = 0; i < s.size()/2; i++) {
            int k = i + 1;
            for (int j = 0; j < k; j++) {
                if (s[j] != s[k]) {
                    break;
                }
                k++;
            }
        }
    }
};

• 本来没思路 看了暴力解法的思路 有了想法 但代码还是写不出来

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

• 看了KMP方法 只能自己写出来这么多

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

• getNext函数 也就是获得前缀表next的函数 虽然思路理解 但代码有的地方一知半解 尤其是遇到了两个错误
  • 关于next数组：
    • 主函数中定义+调用int next[s.size()]; getNext(next, s);
    • 子函数头部＋初始化void getNext(int *next, string s) {其他语句; next[0] = 0; 其他语句;}
  • 关于边界溢出
    • while (j > 0 && s[j] != s[i]) 这句话要加上j > 0这个条件
• 主函数中 那个if判断句
  • 为什么next数组 最后一个元素值 不能取0 因为后面的取余数学运算不允许除数为0
  • 从代码 倒退原因 我看懂了 但是自己写 是写不出来的 总之还是不太理解 需要再看看