459. Repeated Substring Pattern

/**
 * String Manipulations
 *
 * Refer:
 * https://leetcode.com/problems/repeated-substring-pattern/discuss/94334/Easy-python-solution-with-explaination
 *
 * Time Complexity: O(N^2)
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input string.
 */
class Solution1 {
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.length() < 2) {
            return false;
        }

        String newS = s.substring(1) + s.substring(0, s.length() - 1);
        return newS.contains(s);
    }
}

/**
 * String Searching using KMP
 *
 * Refer: 1)
 * https://leetcode.com/problems/repeated-substring-pattern/discuss/94397/C++-O(n)-using-KMP-32ms-8-lines-of-code-with-brief-explanation.
 * 2)
 * https://leetcode.com/problems/repeated-substring-pattern/discuss/94397/C++-O(n)-using-KMP-32ms-8-lines-of-code-with-brief-explanation./98921
 *
 * Time Complexity: O(N)
 *
 * Space Complexity: O(N)
 *
 * N = Length of the input string.
 */
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        if (s == null || s.length() < 2) {
            return false;
        }

        // lps indicates longest proper prefix which is also suffix
        int[] lps = kmpLookupTable(s);
        int len = s.length();

        if (lps[len - 1] != 0 && len % (len - lps[len - 1]) == 0) {
            return true;
        } else {
            return false;
        }
    }

    private int[] kmpLookupTable(String s) {
        int[] lps = new int[s.length()];
        int i = 1;
        int index = 0;
        while (i < s.length()) {
            if (s.charAt(i) == s.charAt(index)) {
                lps[i] = index + 1;
                index++;
                i++;
            } else {
                if (index > 0) {
                    index = lps[index - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
}