C++ O(n) Using KMP Next


  • 0
    F
    class Solution {
        vector<int> next;
        void calcNext(string const & str) {
            next.resize(str.size() + 1);
            next[0] = -1;
            int i = 0, j = -1;
            while (j < (int)str.size() && i < (int)str.size())
                if (j == -1 || str[i] == str[j])
                    next[++ i] = ++ j;
                else
                    j = next[j];
        }
    public:
        bool repeatedSubstringPattern(string str) {
            calcNext(str);
            return str.size() > 1 && next.back() >= str.size() / 2 && str.size() % (str.size() - next.back()) == 0;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.