'''

bool repeatedSubstringPattern(string s) {

size_t len = s.size();

//vector<int> help(len, 0);

int j=0, i=1;

while(i<len)

{

if(s[i] == s[j])//find the potential repeated substr and caculate the duplication count.

{

++i;

++j;

}

else if(j==0) ++i;//has not find complelet repeated substr

else

{

j=s.rfind(s[i], j);

if(j == string::npos) j=0;

//there are same chars in the substr which leads to caculate the duplication count in advance,

//need to trace back to the right position. e.g. abacababacab when j=3 and i=7, needs to trace back to j=1

}

}

return j >= (len-j) && j%(len-j) == 0;//j is duplication count, it should be the multiple of the lenth of repeated substr.

}

'''