> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/02-04-2022-459.md).

# 02/04/2022 459

I think when you finish creating the lps array, In this scenario, the last value will contain the value of the largest substring. If you are deducting it from the length of the entire string, you will get the length of the smallest substring pattern. which is 2 for String ABABAB. Suppose the string is ABCABCABC. ABCABCABC --> KMP Table will be : 0 0 0 1 2 3 4 5 6. The value of the smallest substring will be 3 (ABC --> 9 (Length of the Entire String) - 6 (Last Value of the LPS Array)).

```
When we finish creating the lps array, In this scenario, the last value will contain 
the Length of the largest substring. If we are deducting it from 
the length of the entire string, we will get 
the length of the smallest substring pattern. which 
is 2 for String ABABAB. Suppose the string is ABCABCABC. ABCABCABC --> KMP Table will be : 
0 0 0 1 2 3 4 5 6. The value of the smallest substring will be 3 (ABC --> 9 (Length of the Entire 
String) - 6 (Last Value of the LPS Array)). */
```

// two pointers

Method 1:

For a repeatedSubstringPattern, the time of repeats should at least 2 times. So the max length of the repeat string pattern should be s.length() /2. Then we decrement from the max length, check if the substring pattern length is the divisor of the whole string length. If it is, then we iterate the string and use two pointers i starting from 0 , and i + j to check if the corresponding characters are the same. If same, we increment index i. Finally check if i + l == n.

Time O(n^2)

Space O(1)

```
// Some code
class Solution { 
public boolean repeatedSubstringPattern(String s) { 
    if(s.length() == 0 || s == null) return false; 
    int n = s.length(); 
    for(int l = n/2; l > 0; l--){ // At least there should be 2 substring check. 
        if(n % l == 0){ 
        int i = 0; 
        while(i + l < n && s.charAt(i) == s.charAt(i + l)){ //two pinters to check if the characters are same
            i++; 
        }
        if(i + l == n) return true; 
        } 
    } 
    return false; 
    } 
}
```

Method 2:

Use KMP algorithm to get the common prefix and suffix table for each character. If the string has repeteated string pattern, then the last value of the table would be the longest length of common prefix and suffix (when it is not 0). If you are deducting it from the length of the entire string, you will get the length of the smallest substring pattern. If you use string length mod length of the smallest substring pattern and get 0, that means this string is made of repeated string pattern.

Time O(n)

Space O(n)

class Solution { public boolean repeatedSubstringPattern(String s) { if(s == null || s.length() == 0) return false; int longestPsSubstring = kmpTable(s); int n = s.length(); if(longestPsSubstring != 0 && n % (n - longestPsSubstring) == 0) return true; return false;\
} private int kmpTable(String s){ int\[] table = new int\[s.length()]; int i = 1, j = 0; while(i < s.length()){ if(s.charAt(i) == s.charAt(j)){ j++; table\[i] = j; i++; }else if(j > 0){ j = table\[j -1]; }else{ i++; } } return table\[s.length() - 1]; } }

```
public boolean repeatedSubstringPattern(String str) {
        int len = str.length();
    	for(int i=len/2 ; i>=1 ; i--) {
    		if(len%i == 0) {
    			int m = len/i;
    			String subS = str.substring(0,i);
    			int j;
    			for(j=1;j<m;j++) {
    				if(!subS.equals(str.substring(j*i,i+j*i))) break;
    			}
    			if(j==m)
    			    return true;
    		}
    	}
    	return false;
    }
```

```
public boolean repeatedSubstringPattern(String str) {
	int l = str.length();
	for(int i=l/2;i>=1;i--) {
		if(l%i==0) {
			int m = l/i;
			String subS = str.substring(0,i);
			StringBuilder sb = new StringBuilder();
			for(int j=0;j<m;j++) {
				sb.append(subS);
			}
			if(sb.toString().equals(str)) return true;
		}
	}
	return false;
}
```

```
public boolean repeatedSubstringPattern(String s) {
        int l = s.length();
        for(int i = l/2; i >=1; i--) {
            //only have to check if s can be divided evenly
            if(l % i == 0) {
                // n = how many times the substring would repeat
                int n = l / i;
                String subS = s.substring(0, i);
                if(isTheSubstring(subS, n, s))
                    return true;
            }
        }
        return false;
    }
    
    private boolean isTheSubstring(String subS, int repeat, String s) {
        int len = subS.length();
        for(int i = 1; i < repeat; i++) {
            if(!subS.equals(s.substring(i * len, i * len + len)))
                return false;
        }
        return true;
    }
```

```
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n=s.length();
        for(int i=n/2;i>0;i--){
            if(n%i==0){
                int k=i;
                for(;k<n;k+=i){
                    int j=0;
                    for(;j<i;j++){
                        if(s.charAt(j+k)!=s.charAt(j)) break;
                    }
                    if(j!=i) break;
                }
                if(k==n) return true;
            }
        }
        return false;
    }
}
```