<p>For two strings <code>s</code> and <code>t</code>, we say &quot;<code>t</code> divides <code>s</code>&quot; if and only if <code>s = t + t + t + ... + t + t</code> (i.e., <code>t</code> is concatenated with itself one or more times).</p>

<p>Given two strings <code>str1</code> and <code>str2</code>, return <em>the largest string </em><code>x</code><em> such that </em><code>x</code><em> divides both </em><code>str1</code><em> and </em><code>str2</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;ABCABC&quot;, str2 = &quot;ABC&quot;
<strong>Output:</strong> &quot;ABC&quot;
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;ABABAB&quot;, str2 = &quot;ABAB&quot;
<strong>Output:</strong> &quot;AB&quot;
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> str1 = &quot;LEET&quot;, str2 = &quot;CODE&quot;
<strong>Output:</strong> &quot;&quot;
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= str1.length, str2.length &lt;= 1000</code></li>
	<li><code>str1</code> and <code>str2</code> consist of English uppercase letters.</li>
</ul>

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        if(str1 == str2) return str1;
        // If str1 and str2 have a common divisor then one of them will be a substr of the other gcd*m vs gcd*n
        string common;
        int m = str1.length();
        int n = str2.length();
        int i=0;
        while(i<m && i<n && str1[i] == str2[i]) { 
            common.push_back(str1[i]);
             ++i;
        }

        if(i !=m && i!=n) return "";
        cout << "Common substring : " << common << endl;

        // Now the remaining part of the larger string also need to be checked whether it satisfies gcd*(|m-n|)
        // Either the entirity of the common string is the gcd or part of it like 1/2 or 1/3 or 1/4
        i = 0;
        string gcd;
        string cd; cd.push_back(str1[i]);
        // Check weather this is a common denominator
        while (cd.length() <= common.length()) {
            cout << "checking whether " << cd << " is a common denominator" << endl;
            int start = 0;
            int length = cd.length();
            while(start+length <= common.length() && common.substr(start, length) == cd) {
                start = start + length;
            }
            if(start == common.length()) {
                // We need to check whether cd is cd for the rest of the longer string
                string tmp = m > n? str1 : str2;
                while(start+length <= tmp.length() && tmp.substr(start, length) == cd) {
                   //cout << "Found " << cd << " in " << tmp << " starting at " << start << endl;
                   start = start + length; 
                }
                if(start == tmp.length()) {
                    //cout << cd << " is a cd for rest of tmp : " << tmp << "  start = " << start << endl;
                    gcd = cd;
                }
            }
                i++;
                cd.push_back(common[i]);
            
        }

        return gcd;
    }
};
17478