Repeated Substring Pattern

Info

Requires the Knuth Morris Pratt Algorithm in order to solve optimally. I tried to solve this problem with my own algorithm, but failed at: abacababacab since I failed to reset to the right position.

Brute Force Answer

• For each index up to the middle, check if that multiplied by its divisor (number of times it divides equally with the entire string) itself equals the string. If it does, return true, and otherwise false.

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        for i in range(1, n // 2 + 1):
            if n % i == 0: # Look at only substrings where the length of that substring divides n evenly
                if s[:i] * (n // i) == s: # Concatenate with the remaining letters left and check if that equals the original string
                    return True
 
        return False
            

---

References

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