Repeated Substring Pattern - Simple Java Solution, using KMP


  • 5
    V
    public class Solution {
        /* KMP pattern table construction part */
        public boolean repeatedSubstringPattern(String str) {
            int n = str.length(), cur = 0, j = 1;
            int[] pattern = new int[n];
            pattern[0] = 0;
            
            while( j<n ) {
                if( str.charAt(cur) == str.charAt(j) ) {
                    pattern[j++] = ++cur;
                }
                else {
                    if( cur == 0 )  pattern[j++] = 0;
                    else cur = pattern[cur-1]; /* start from beginning of current matching pattern */
                }
            }
            
            return (pattern[n-1] > 0 && n%(n-pattern[n-1]) == 0);
        }
    }
    

  • 1
    S

    You need to describe how you got the solution and also what your solution is doing. KMP is okay, I understood that. But, can you please explain why "n%(n-pattern[n-1] "?


  • 0
    D

    @SanD just consider two test case "abc abc abc abc" and "abc abc abc abc abc".
    first case, pattern[n-1]=9 12%(12-9)=0
    second case, pattern[n-1]=12 15%(15-12)=0;
    in fact, the input has to be in the format of above two cases to pass the test.


  • 1
    V

    @SanD Basically he is saying, the array constructed by kmp method will contain the number of characters in prefix that match the suffix till that position. So if array[last_position] == 0 , that means there are no matching prefix , which basically means the string is not in repeated format.
    As a second point, he checks whether the length of the substring is a divisor of length of string. so he does len_of string % [len_of string - len of prefix] == 0. I think one needs to understand the logic behind kmp array construction to do via this method. Nevertheless solves it in O(N) which is good


Log in to reply
 

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