BinarySearch 0675 Longest Prefix that Is a Suffix

Problem statement

https://binarysearch.com/problems/Longest-Prefix-that-Is-a-Suffix/

Solution

Equal to 1392. Longest Happy Prefix.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, s):
        p = [0] * len(s)
        for i in range(1, len(s)):
            k = p[i - 1]
            while k > 0 and s[k] != s[i]:
                k = p[k - 1]
            if s[k] == s[i]:
                k += 1
            p[i] = k
        return s[:p[-1]]