package string;

/**
 * Created by gouthamvidyapradhan on 25/03/2017.
 Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

 Example 1:
 Input: "abab"

 Output: True

 Explanation: It's the substring "ab" twice.
 Example 2:
 Input: "aba"

 Output: False
 Example 3:
 Input: "abcabcabcabc"

 Output: True

 Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
 */
public class RepeatedSubstringPattern
{
    /**
     * Main method
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception
    {
        System.out.println(new RepeatedSubstringPattern().repeatedSubstringPattern("a"));
    }

    public boolean repeatedSubstringPattern(String s)
    {
        boolean found;
        for(int i = 1, l = s.length(); i < l; i ++)
        {
            found = true;
            String subI = s.substring(0, i);
            int j = i;
            if(j >= l) return false;
            while(j < l)
            {
                if((j + i) >= l + 1)
                    return false;
                String subJ = s.substring(j , j + i);
                if(!subI.equals(subJ))
                {
                    found = false;
                    break;
                }
                j += i;
            }
            if(found) return true;
        }
        return false;
    }
}