Simple and most fast solution neither KMP nor string rotation


  • 0
    M

    '''
    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.
    }
    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.