Repeated Substring - KMP related

KMP related | Hello World
有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为2，输入一个String写代码返回T或者F
例子：
"abcabcabc" Ture 因为它把abc重复3次构成
"bcdbcdbcde" False 最后一个是bcde
"abcdabcd" True 因为它是abcd重复2次构成
"xyz" False 因为它不是某一个String重复
"aaaaaaaaaa" False 重复的短String长度应至少为2（这里不能看做aa重复5次)
要求算法复杂度为O(n)

public int [] failure(String s) {

    int [] f = new int[s.length() + 1];

    f[0] = f[1] = 0;

    int j = 0; // record  the last possible position to extend

    for(int i = 1; i < f.length - 1; i++) {

        if (s.charAt(i-1) == s.charAt(k)) {

            f[i+1] = k+1;

            k++;

        }

        else if (k != 0) {

            k = f[k];

            i--; // try next k with same i

        }

        else {

            f[i+1] = 0;

        }

    }

    return f;

}

public static String minConcat(String s) {

    int [] f = failure(s);

    int n = f[s.length()];

    String concast = s;

    while(n != 0) {

        if (n%(s.length() - n) == 0) { //n should be greater thatn s.length() - n if not, the statement will not be 0.

            concast = s.substring(0, s.length() - n);

        }

        n = f[n];

    }

    return concast;

}

http://codeanalysis111.blogspot.com/2014/11/string-question-example-using-kmp.html
用KMP吧。检查preprocess部分生产的array pai 就可以了。如果是valid case. 
preprocessing array 必然满足下面的几个条件：
1. pai[n-1] 必须是最大值 (这个没必要专门检查,只要3满足就成);
2. s[0,...,n-pai[n-1])就是repeating pattern;
3. pai[n-1]/(length of the repeating pattern) >= 1;
4. pai[n-1] % (length of the repeating pattern) == 0. 

bool isMultiple(const string &text){
    int n=text.length();
    vector<int> pai(n);
    computeVec(text,pai);
    int len=n-pai[n-1];
    return len>1&&pai[n-1]/len>=1&&pai[n-1]%len==0;
}

void computeVec(const string &Pat, vector<int>&pai){//from KMP
    pai[0]=0;
    int k=0;
    int m=Pat.length();
    for(int i=1;i<m;i++){
        while(k>0&&Pat[k]!=Pat[i])
            k=pai[k-1];
        if(Pat[k]==Pat[i])
            k++;
        pai[i]=k;
    }
}
X. http://yuanhsh.iteye.com/blog/2172670
patternPos表示从哪里开始匹配。初始值为0。
patternEnd表示模式结束的位置。初始值为0。

当前字符和patternPos不相等的话，说明pattern不成立，patternPos回到开始位置0，patternEnd设为当前字符所在位置i。

当前字符和patternPos相等的话，patternPos加1移到下一个位置，patternEnd保持不变。并检查下如果patternPos超过patternEnd的话，说明截止到当前字符成功匹配，patternPos回到开始开始匹配下一串字符。注意，当i走到最后的话，patternPos就不用清0了。

最后判断成功的条件是，patternPos大于patternEnd的时候，说明整个字符串pattern且至少重复pattern两次。patternEnd大于零，说明pattern长度大于1。

1. public boolean isMultipleDuplicate(String s) {  
2.     int patternPos = 0, patternEnd = 0;  
3.     for(int i=1; i<s.length(); i++) {  
4.         if(s.charAt(i) != s.charAt(patternPos)) {  
5.             patternPos = 0;  
6.             patternEnd = i;  
7.         } else {  
8.             if(++patternPos > patternEnd && i != s.length()-1) {  
9.                 patternPos = 0;  
10.             }  
11.         }  
12.     }  
13.     return patternPos>patternEnd && patternEnd>0;  
14. }  

http://www.mitbbs.com/article_t/JobHunting/32633319.html
Read full article from KMP related | Hello World