오늘 문제는 기초 KMP 알고리즘을 사용. KMP알고리즘 자체 난이도는 좀 있는 편.


class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if len(haystack) < len(needle):
return -1
def get_pi(pat):
n = len(pat)
pi = [0] * n
i = 1
j = 0
while i<n:
if pat[i] == pat[j]:
j += 1
pi[i] = j
i += 1
else:
if j:
j = pi[j-1]
else:
pi[i] = j
i += 1
return pi

def kmp(txt, pat):
pi = get_pi(needle)
i = j = 0
while i<len(txt):
if txt[i] == pat[j]:
i += 1
j += 1
if j == len(pat):
return i - len(pat)
else:
if j:
j = pi[j-1]
else:
i += 1
return -1

return kmp(haystack, needle)