string question: example using kmp

A家的电面题:

有一种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 boolean isMultiple(String s){

}


Ans:

用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;
    }
}