459_Repeated_Substring_Pattern

Leetcode 459: Repeated Substring Pattern
Detailed video Explanation: https://youtu.be/p92_kEjyJAo
=============================================


C++:
----
class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.length();
        vector<int> lps(n, 0);
        for(int i = 1; i < n; ++i){
            int j = lps[i-1];
            while(j > 0 && s[i] != s[j]) j = lps[j-1];
            if(s[i] == s[j]) ++j;
            lps[i] = j;
        }
        int l = lps[n-1];
        return (l != 0) && (l % (n-l) == 0);
    }
};



Java:
-----
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;
        }
        int l = lps[n-1];
        return (l != 0) && (l % (n-l) == 0);
    }
}



Python3:
--------
class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        n = len(s)
        lps = [0]*n
        for i in range(1, n):
            j = lps[i-1]
            while j > 0 and s[i] != s[j]: j = lps[j-1]
            if s[i] == s[j]: j += 1
            lps[i] = j
        l = lps[n-1]
        return l != 0 and (l % (n-l) == 0)