Java & O(n)


  • 38
    C
    public boolean repeatedSubstringPattern(String str) {
    	        //This is the kmp issue
    	        int[] prefix = kmp(str);
    	        int len = prefix[str.length()-1];
    	        int n = str.length();
    	        return (len > 0 && n%(n-len) == 0);
    	    }
    	    private int[] kmp(String s){
    	        int len = s.length();
    	        int[] res = new int[len];
    	        char[] ch = s.toCharArray();
    	        int i = 0, j = 1;
    	        res[0] = 0;
    	        while(i < ch.length && j < ch.length){
    	            if(ch[j] == ch[i]){
    	                res[j] = i+1;
    	                i++;
    	                j++;
    	            }else{
    	                if(i == 0){
    	                    res[j] = 0;
    	                    j++;
    	                }else{
    	                    i = res[i-1];
    	                }
    	            }
    	        }
    	        return res;
    	    }

  • 0
    A

    @chnsht Thanks for the awesome solution. Just wanted to know the significance of:
    n%(n-len) == 0 ?


  • 9
    C

    @aman13
    Because in the prefix array, the number means longest prefix and also suffix. So
    n-len: the length of prefix(should be the repeated sequence),
    n%(n-len): check if the candidate sequence is the answer(if it is the answer, the array should not have remains). Hope this helps.


  • 8
    C

  • 1
    J

    If anyone is stuck with understanding kmp, I found this explanation is pretty clear. Please check it out:

    http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/


  • 0
    T

    excellent solution! Simulate KMP method!

    public class Solution {
        public boolean repeatedSubstringPattern(String s) {
            int[] pre=kmp(s);
            int len=pre[pre.length-1];
            
            if(len>0&&pre.length%(pre.length-len)==0){
                return true;
            }
            
            return false;
            
        }
        
        public int[] kmp(String s){
            char[] array = s.toCharArray();
            int i=0;
            int j=1;
            int[] pre=new int[array.length];
            pre[0]=0;
            while(j<array.length){
                if(array[i]==array[j]){
                    pre[j]=i+1;
                    i++;
                    j++;
                }else{
                    if(i!=0){
                        i=pre[i-1];
                    }else{
                        pre[j]=0;
                        j++;
                    }
                }
            }
            
            return pre;
        }
    }
    
    

  • 0
    I
    This post is deleted!

  • 0
    B

    What's the time complexity of kmp()?. Seems like O(n^2) because i could go back to 0 for each j.


  • 1
    Y

    @bluecloud build kmp is O(n). i will increase at most n times and thus decrease at most n times and total is n+n=O(n)
    you can find more detailed discussion below:
    https://leetcode.com/problems/shortest-palindrome/solution/#approach-3-kmp-accepted


  • 0
    Y

    @aman13 It is the most important part.


  • 0
    L

    @chnsht why i=res[i-1]?


  • 0
    L

    @tiandiao123 if(i!=0) why i=pre[i-1]?


  • 0
    K

    @chnsht Hi

    Can you explain how did you determine that substring is 3 char long by subtracting

    str.length() - Value at Last Index in Prefix []

    I understood KMP logic first time but still unable to digest this idea of n-len in below line.

    n%(n-len) == 0


  • 0
    L

    @kotak86
    The value at last in kmp computed array has the value of the substring present.
    eg: string ="abcabc" now the value at computed array will be 3 at c.
    This we are taking and subtracting from the length of string
    length of string:"len =6"
    since it divides completely we make sure that the string is completely built with substring.

    Now see if the input is "abcdabc" len=7
    Our kmp array will still have 3
    now the the string cannot be divided just with substring length that means it wont be constructed with the substring alone. Hope this is clear :)


Log in to reply
 

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