Amazon Interview - Check string is multiple duplicate

有一种String,是把一个更短的String重复n次而构成的，那个更短的String长度至少为2，输入一个String写代码返回true或者false

例子：
"abcabcabc"  true   因为它把abc重复3次构成
"bcdbcdbcde" false  最后一个是bcde
"abcdabcd"   True   因为它是abcd重复2次构成
"xyz"       false  因为它不是某一个String重复
"aaaaaaaaaa"  false  重复的短String长度应至少为2（这里不能看做aa重复5次)
要求算法复杂度为O(n)

 

Solution:

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。

public boolean isMultipleDuplicate(String s) {
    int patternPos = 0, patternEnd = 0;
    for(int i=1; i<s.length(); i++) {
        if(s.charAt(i) != s.charAt(patternPos)) {
            patternPos = 0;
            patternEnd = i;
        } else {
            if(++patternPos > patternEnd && i != s.length()-1) {
                patternPos = 0;
            }
        }
    }
    return patternPos>patternEnd && patternEnd>0;
}

Output: 

abcabcabc: true
bcdbcdbcde: false
abcdabcd: true
xyzxy: false
aaaaaaaaaa: false
ABABCABABC: true
bcdbcdbcdebcdbcdbcde: true
ababeabab: false
ababab: true
bcdbcdbcdbcdbcdbc: false
abcabcabcab: false

另外，上面的代码还可以加判断:patternEnd > s.length() / 2,走过一半就可以结束了；
以及 s.length() % (patternEnd + 1) != 0, ++i, ++patternEnd，过滤掉长度不符合的情况。

我们还可以用KMP来解这题，具体看这里：
https://hellosmallworld123.wordpress.com/2014/06/10/kmp-related/