String by iterating substring

Given a string ‘str’, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Examples:

Input: str = "abcabcabc"
Output: true
The given string is 3 times repetition of "abc"

Input: str = "abadabad"
Output: true
The given string is 2 times repetition of "abad"

Input: str = "aabaabaabaab"
Output: true
The given string is 4 times repetition of "aab"

Input: str = "abcdabc"
Output: false

本题参考了kmp算法 http://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/

这个题用了kmp中算pattern算prefex和surfex的code，题目认为，如果n能够整出n-max的话，就能构成。max是所能形成的最长的prefix和postfex.其实想不到最后那个整除，

    public static boolean findIt(String s){
        char[] pattern = s.toCharArray();
        int res = 0;
        int index = 0;
        int[] lps = new int[pattern.length];
        for(int i = 1; i < pattern.length;){
            if(pattern[i] == pattern[index]){
                lps[i] = index + 1;
                i++;
                index++;
            }else{
                if(index != 0){
                    index = lps[index - 1];
                }else{
                    index = 0;
                    i++;
                }
            }
        }
        int max = lps[pattern.length - 1];
        if(s.length() % (s.length - max)){
            return false;
        }
        return true;