C++ O(N) using KMP


  • 0
    G
    class Solution {
    public:
        bool repeatedSubstringPattern(string s) 
        {
            if(s.empty())
            {
                return (true);
            }
            
            //
            // KMP table
            //
            vector<int> V(s.size(),0);
            
            for(int i = 0,j = 1;j < s.size();)
            {
                if(s[j] == s[i])
                {
                    V[j] = i + 1;
                    i++;
                    j++;
                }
                else if(i == 0)
                {
                    j++;
                }
                else
                {
                    i = V[i - 1];
                }
            }
            
            if(V[s.size() - 1] == 0)
            {
                return false;
            }
            
            int Diff = s.size() - V[s.size() - 1];
            
            string D = s.substr(0,Diff);
            string Other = s.substr(V[s.size() - 1]);
            
            return (D == Other);
        }
    };

Log in to reply
 

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