Longest Periodic Proper Prefix

Time: O(n)

Space: O(n)

Intuition

Find length of longest proper prefix of string that is also a suffix with period dividing string length. KMP failure function.

Algorithm

1Compute KMP failure function (lps). Answer related to lps[n-1] if length divides n.

Common Pitfalls

•Period check: if (n % (n - lps[n-1])) == 0: string has period n-lps[n-1]. Longest proper periodic prefix = lps[n-1].

Longest Periodic Proper Prefix.java

Java

// Approach: KMP failure function. lps[i] = longest proper prefix of s[0..i] which is also a suffix.
// Time: O(n) Space: O(n)
class Solution {
    int getLongestPrefix(String s) {
        int n = s.length();
        int i = 0;
        int j = n - 1;
        int pos = n - 1;
        int ans = 0;
        while (j < n && pos > 0) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j++;
                ans++;
            } else {
                i = 0;
                pos--;
                j = pos;
                ans = 0;
            }
        }
        
        if (pos == 0)
            return -1;

        return n - ans;
    }
}

Was this solution helpful?