[Leetcode] 686. Repeated String Match (re) C++

Repeated String Match - LeetCode

O(n²)로 a가 커질 때마다 확인하는 식으로 짰는데, 너무 길어져 버리면 Time Limit이 되어버림

 

class Solution {
public:
    int repeatedStringMatch(string a, string b) 
    {
        int count = 1;
        string a_plus = a;
        
        if(b.size() > 100)
            return -1;
        
        for(int i=0; i<b.size(); i++)
        {
                
            
            if(a_plus.size() >= b.size())
                for(int k = 0; k<= a_plus.size() - b.size(); k++)
                {
                    string sub = a_plus.substr(k,b.size());    
                    
                    if(sub.compare(b) == 0)
                        return count;
                }

                
            
            a_plus += a;
            count++;
            

        }
        
        return -1;
    }
};