Untitled

class Solution {
    public  int[] LPS(String s){
        int n = s.length();
        int[] lpf = new int[n];
        for(int i = 0, j = 1; j < n; ){
            while(j < n && s.charAt(i) == s.charAt(j)){
                ++i;
                lpf[j++] = i;
            }
            if(i > 0) i = lpf[i-1];
            else ++j;
        }
        return lpf;
    }

    public String gcdOfStrings(String str1, String str2) {
        int n = str1.length(), m = str2.length();
        if(n > m){
            int temp = m;
            m = n;
            n = temp;
            String tempStr = str1;
            str1 = str2;
            str2 = tempStr;
        }
        int[] lps = LPS(str1);
        String gcd = str1.substring(0, n - lps[n-1]);
        if(n % gcd.length() != 0 || m % gcd.length() != 0){
            return "";
        }
        int gcdSize = gcd.length();
        ArrayList<Integer> dvs = new ArrayList<Integer>();
        for(int i = 1; i <= n/i; ++i){
            if(n % i == 0){
                dvs.add(i);
                if(i != n / i){
                    dvs.add(n/i);
                }
            }
        }

        dvs.sort(Comparator.reverseOrder());
        for(int x : dvs){
            if(x < gcdSize) continue;
            StringBuilder newGcd = new StringBuilder();
            for(int i = 0; i < x / gcdSize; ++i){
                newGcd.append(gcd);
            }
            boolean ok = true;
            for(int j = 0; j < m; j += newGcd.length()){
                if(j + newGcd.length() > m || !str2.substring(j, j + newGcd.length()).equals(newGcd.toString())){
                    ok = false;
                    break;
                }
            }
            if(ok) {
                System.out.println(newGcd.length());
                return newGcd.toString();
            }
        }
        return "";  
    }
}