Leetcode-459-Repeated Substring Pattern

Repeated Substring Pattern

leetcode: https://leetcode.com/problems/repeated-substring-pattern/

Description:

Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.

Idea:

Step1: us KMP to get the prefix table of the string.

Step2: The length of the string - the longest length(suffix == prefix) of the string = the repeated substring’s length

Step3: If the length of string % the repeated substring’s length =0, it menas the original strings consists of the substring.

Code:

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

    }
}