[数据结构与算法]LeetCode 459. 重复的子字符串 KMP解法

使用KMP的next来解
自己写的代码，比较粗糙

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        if(s.size() == 1)
            return false;
        //创建next表
        int *next = new int[s.size()];
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++)
        {
            while(j > -1 && s[j + 1] != s[i])
                j = next[j];
            if(s[j + 1] == s[i])
                j++;
            next[i] = j;
        }
        
        //题目处理
        if(next[s.size() - 1] == -1)
            return false;
        int d = s.size() - 1 - next[s.size() - 1];
        int i = s.size() - 1;
        for(; i >= 0; i -= d)
        {
            if(s[i] != s[s.size() - 1])
                return false;
        }
        if(i != -1)
            return false;
        return true;
    }
};

把处理部分进行一下优化

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int l = s.size();

        int *next = new int[l];
        int j = -1;
        next[0] = j;
        for(int i = 1; i < l; i++)
        {
            while(j > -1 && s[j + 1] != s[i])
                j = next[j];
            if(s[j + 1] == s[i])
                j++;
            next[i] = j;
        }

        if(next[l - 1] == -1 || l % (l - 1 - next[l -1 ]) != 0)
            return false;
        return true;
    }
};

与50位技术专家面对面

20年技术见证，附赠技术全景图