/*
Find whether a given string s is divisible by string t. If it is
divisible, find the length of the smallest string x such that if x is concatenated any
 number of times, we get both s and t. If this is not
 possible, then print -1. Help find the length of the smallest string x.
 A string s is said to be divisible by string t if string t can be
 concatenated some number of times to get string s.

Constraints

1 ≤ size of s ≤ 2 x 10^5
1 ≤ size of t ≤ 2 x 10^5
size of t ≤ size of s

 Example:
 s = bcdbcdbcd
 t = bcdbcd
 If string t is concatenated twice, the result
 is bcdbcdbcdbcd > s. String s is not divisible by string t, so
 the result is -1.

 Example:
 s = bcdbcdbcdbcd
 t = bcdbcd

 If string t is concatenated twice, the result
 is bcdbcdbcdbcd = s. String s is divisible by string t. The
 smallest string x that can be concatenated to create both
 strings s and t is bcd. Its length is 3.

Sample Input
lrbb
lrbb
Sample Output
4
Explanation
If string "lrbb" is concatenated 1 time, we get string
s and string t.

Sample Input
rbrb
rbrb
Sample Output
2
Explanation
If string "rb" is concatenated 2 times, we get string
s and string t.

*/

    private static int makeLPSArray(String str, int index,
                                     int lps[], int longestSubLength) {
        int len = 0;
        int i = 1;
        lps[0] = 0;

        while (i < index) {
            if (str.charAt(i) == str.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            }
            else {
                if (len > 0) {
                    len = lps[len-1];
                }
            }
        }
        return longestSubLength;
    }

    private static int calcRepetitions(String text, String sub) {
        //for every text.substring(sub)
        int reps = 0;
        if(text.length() % sub.length() == 0){
            for(int i = 0; i < text.length() &&
                    i + sub.length() - 1 < text.length(); i++) {
                if(text.substring(i, i + sub.length()).equals(sub)){
                    reps++;
                    i += sub.length() - 1;
                }
            }
        }

        return reps;
    }

    public static int findSmallestDivisor(String s, String t) {
        int tReps = 0;
        int sReps = 0;
        int minDivisorSize = -1;
        if(s.length() % t.length() == 0) {

            for (minDivisorSize = 1; minDivisorSize < t.length(); minDivisorSize++) {
                String repeat = t.substring(0, minDivisorSize);
                tReps = calcRepetitions(t, repeat);
                sReps = calcRepetitions(s, repeat);

                if (sReps != 0 && tReps != 0 && tReps <= sReps)
                    return minDivisorSize;
            }

        }

        return minDivisorSize;
    }