C++ O(n) using KMP, 32ms, 8 lines of code with brief explanation.


  • 22
    J

    First, we build the KMP table.

    1. Roughly speaking, dp[i+1] stores the maximum number of characters that the string is repeating itself up to position i.
    2. Therefore, if a string repeats a length 5 substring 4 times, then the last entry would be of value 15.
    3. To check if the string is repeating itself, we just need the last entry to be non-zero and str.size() to divide (str.size()-last entry).
        bool repeatedSubstringPattern(string str) {
            int i = 1, j = 0, n = str.size();
            vector<int> dp(n+1,0);
            while( i < str.size() ){
                if( str[i] == str[j] ) dp[++i]=++j;
                else if( j == 0 ) i++;
                else j = dp[j];
            }
            return dp[n]&&dp[n]%(n-dp[n])==0;
        }
    

  • 14
    O

    Same implementation.

    My p[i] stands for longest common string length of prefix string and the string ended with position i.

    The important point is the last one: len % (len - p[len - 1]) == 0

    for a string like below, if p[len-1] = 15, len=20:

    #####~~~~~^^^^^$$$$$
    #####~~~~~^^^^^$$$$$

    by p[len-1] = 15, we know the strings colored red are the same.

    so you can infer that:

    ##### == ~~~~~

    ~~~~~ == ^^^^^

    ^^^^^ == $$$$$

    The whole is repeating as #####

    the length of it is 5, which can be completely divided by len.

    That's how this final condition works.

    bool repeatedSubstringPattern(string str) {
            int len = str.length(), i = 0, j = 1;
            int p[len];
            while (j < len)
                if (str[i] == str[j])
                    p[j++] = ++i;
                else {
                    if (!i) 
                        p[j++] = 0;
                    else
                        i = p[i - 1];
                }
            return p[len - 1] && len % (len - p[len - 1]) == 0;
        }
    

  • 1

    really wonderful idea!!!


  • 0
    S

    Same idea but more Simple version

    public:
        bool repeatedSubstringPattern(string str) {
            int k = -1, m = str.size(), pi[m+1] = {-1};
            for(int i=1; i <= m; i++){
                while(k>=0 && str[k]!=str[i-1]) k = pi[k];
                pi[i] = ++k;
            }
            return pi[m]&&(pi[m]%(m-pi[m])==0);
        }
    };
    

  • 0
    T

    @jade86 - in your solution, shouldnt you return false at the point of first mismatch after you have a non-zero value of j, .... i.e. at the line
    -->else j=dp[j];


  • 0
    Z

    @ofLucas said in C++ O(n) using KMP, 32ms, 8 lines of code with brief explanation.:

    len % (len - p[len - 1]) == 0;

    What I agree is that:
    if len % (len - p[len - 1]) == 0, then the pattern is repeated.

    However, if len % (len - p[len - 1]) != 0, can we lead to the conclusion that pattern is not repeated? Do we need to recursively check p[p[len - 1] - 1] and so on?

    In other words, I agree that len % (len - p[len - 1]) == 0 is a sufficient condition for the statement that pattern is repeated, but may not be a necessary condition.

    Any comment on it? Thx.


  • 0
    R

    @tobe4321 I think you can try the case "abaaba"


  • 0
    R

    @Zhen_Li p[n] means the substr(0, p[n]) is the same with the substr(n - p[n], p[n]). Assume x = len / (len - p[len - 1]), y = len % (len - p[len - 1]), we must have x*(len - p[len - 1]) + y = len. If y != 0, since y < len - p[len-1], it's definitely not a repeated substring.


  • 0
    L

    Brilliant code & solution!


Log in to reply
 

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