My one-line c++ solution


  • 10
    X
    bool repeatedSubstringPattern(string str) 
        {
            return (str + str).substr(1, str.size() * 2 - 2).find(str)!=-1;
        }
    

  • 0
    N

    @Xianming.Chen

    @Xianming.Chen said in My one-line c++ solution:

    bool repeatedSubstringPattern(string str) 
        {
            return (str + str).substr(1, str.size() * 2 - 2).find(str)!=-1;
        }
    

    This is great and I cannot believe it is only 3 points!!


  • 0
    X

    @neoly1983
    Thanks, appreciate your compliment.


  • 1
    G

    This is a great solution. I have no idea why it works!
    Can you please explain a bit?


  • 0
    D

    That's fantastic. But how does it work? You got me confused.


  • 0
    Z

    Time complexity O(n^2)


  • 0
    X

    @zestypanda You can implement find function with "Sunday method" for string matching, then the time complexity would be O(2N+N), which is O(N).


  • 2
    X

    @gymf123 Think about this way:
    str + str means doubling, (str + str).substr(1, str.size() * 2 - 2) means removing the first char of the first half and the last char of the second half.

    1. If there is no pattern, both of the first copy and the second copy will be changed, so str will not be found in (str + str).substr(1, str.size() * 2 - 2).
    2. If there is a pattern, the first char of str can still be found in the first half, and the last char of str can also be found in the second half. Here is an example: abcabc is the original string, and (bcabc abcab) includes abcabc.

  • 1
    X

    @daniel_dr Think about this way:
    str + str means doubling, (str + str).substr(1, str.size() * 2 - 2) means removing the first char of the first half and the last char of the second half.

    1. If there is no pattern, both of the first copy and the second copy will be changed, so str will not be found in (str + str).substr(1, str.size() * 2 - 2).
    2. If there is a pattern, the first char of str can still be found in the first half, and the last char of str can also be found in the second half. Here is an example: abcabc is the original string, and (bcabc abcab) includes abcabc.

  • 0
    X

    @zestypanda Here is my version of Sunday method for finding a destination string in a source string.

    int strStr(string src, string dst)
    {
    int len1=src.size(),len2=dst.size(),pos=0;
    while(len2+pos<=len1)
    {
    int count=0;
    while(count<len2&&dst[count]==src[count+pos])
    count++;
    if(count==len2)
    return pos;
    int rightNext=pos+len2,shift=1;
    for(shift=1;shift<=len2;shift++)
    if(src[rightNext]==dst[len2-shift])
    break;
    pos+=shift;
    }
    return -1;
    }

    https://csclub.uwaterloo.ca/~pbarfuss/p132-sunday.pdf


  • 0
    X
    Here is my version of Sunday method for finding a destination string in a source string. 
    
    int strStr(string src, string dst)
        {
            int len1=src.size(),len2=dst.size(),pos=0;
            while(len2+pos<=len1)
            {
                int count=0;
                while(count<len2&&dst[count]==src[count+pos])
                    count++;
                if(count==len2)
                    return pos;
                int rightNext=pos+len2,shift=1;
                for(shift=1;shift<=len2;shift++)
                    if(src[rightNext]==dst[len2-shift])
                        break;
                pos+=shift;
            }
            return -1;
        }
    
    https://csclub.uwaterloo.ca/~pbarfuss/p132-sunday.pdf
    
    

  • 0
    A

    @Xianming.Chen thumbs up for the awesome explanation


Log in to reply
 

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