Problem link
https://leetcode.com/problems/longest-happy-prefix/
Problem Summary
접두사와 접미사가 같은 가장 긴 접두사를 출력하는 문제.
Solution
딱 보니 그 유명한 KMP 이다.
KMP는 현재 인덱스에서 suffix와 같은 prefix의 최대 길이를 구해놓는데, 이를 그대로 사용하면 된다.
KMP 는 로이형의 유튜브를 참고하면 이해하기 쉽다.
https://www.youtube.com/watch?v=GTJr8OvyEVQ
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]]