C++ O(n) KMP


  • 1
        bool repeatedSubstringPattern(string str) {
            vector<int> kmp(str.size(), 0);
            for (int i = 1, j = 0; i < str.size(); i++) {
                while (j > 0 && str[j] != str[i])
                    j = kmp[j - 1];
                if (str[j] == str[i]) 
                    kmp[i] = ++j;
            }
            return kmp[str.size() - 1] && str.size() % (str.size() - kmp[str.size() - 1]) == 0;
        }
    };
    

Log in to reply
 

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