42-Repeated-Substring-Pattern.md

Repeated Substring Pattern

Problem Link

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

---

Pattern

• String
• KMP

---

Approach

Use KMP failure function. If string is composed of repeated substring, lps[n-1] will be > n/2.

---

Time Complexity

O(n)

Space Complexity

O(n)

---

Java Solution

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        int[] lps = new int[n];
        for (int i = 1; i < n; i++) {
            int j = lps[i - 1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) j = lps[j - 1];
            if (s.charAt(i) == s.charAt(j)) j++;
            lps[i] = j;
        }
        return lps[n - 1] > 0 && n % (n - lps[n - 1]) == 0;
    }
}