1392. Longest Happy Prefix

[zeikar]

Problem link

https://leetcode.com/problems/longest-happy-prefix/

Problem Summary

접두사와 접미사가 같은 가장 긴 접두사를 출력하는 문제.

Solution

딱 보니 그 유명한 KMP 이다.
KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 그대로 사용하면 된다.

KMP 는 로이형의 유튜브를 참고하면 이해하기 쉽다.
https://www.youtube.com/watch?v=GTJr8OvyEVQ

<iframe width="560" height="315" src="https://www.youtube.com/embed/GTJr8OvyEVQ" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen></iframe>

Source Code

class Solution:
    def longestPrefix(self, s: str) -> str:
        def kmp(s):
            i, j = 1, 0
            n = [0] * len(s)
            while i < len(s):
                if s[i] == s[j]:
                    n[i] = j + 1
                    i += 1
                    j += 1
                elif j > 0:
                    j = n[j - 1]
                else:
                    n[i] = 0
                    i += 1
            return n

        return s[:kmp(s)[-1]]