Repeated Substring Pattern

LeetCode Q 459 - Repeated Substring Pattern

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Solution

Algorithm: KMP Algorithm
Since we need to find the repeated pattern of the string, we can use KMP Algorithm.

• KMP is usually used to solve Pattern Matching Substring Search problem. It can pre-calculate the longest length L of proper prefix which is also a suffix costs O(n) time and O(n) space.
• The basic idea behind KMP is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window. We take advantage of this information to avoid matching the characters that we know will anyway match.
• We use a table to store this information.
  int[] table = new int[str.length()];
  table[i] denotes the longest prefix which is also proper suffix.

Code:

public boolean repeatedSubstringPattern(String s) {
    if (s == null || s.length() <= 1)
        return false;
    int len = s.length();
    int[] prefix = new int[len];
    int i = 0, j = 1;
    while (j < len) {
        if (s.charAt(i) == s.charAt(j)) {
            prefix[j++] = ++i;
        } else if (i == 0) {
            j++;
        } else if (i != 0) {
            i = prefix[i - 1];
        }
    }
    return prefix[len - 1] != 0 && len % (len - prefix[len - 1]) == 0;
}