8. Find the Index of the First Occurrenc

LeetCode 갤러리
마이너

자동 짤방 이미지

이미지가 없습니다.

자동 짤방으로 사용할 이미지를 등록해 주세요.

Eat, Sleep, LeetCode, Repeat

매니저

부재중입니다.(ddakgun)

부매니저

흑화뉴비(coderhs)

개설일

2022-12-26

ㅇㅇ(46.165) 2023.03.03 09:40:42

조회 30 추천 0 댓글 0

오늘 문제는 기초 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)

고정닉 0

전체 댓글 0개

등록순 최신순 답글순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	제목	글쓴이	작성일	조회	추천
설문	2025년 가장 기억에 남는 인터넷 이슈는?	운영자	25/12/22	-	-
275	57. Insert Interval	흑화뉴비	24.03.18	30	0
274	2485. Find the Pivot Integer	흑화뉴비	24.03.13	24	0
273	1750. Minimum Length of String After Del	흑화뉴비	24.03.06	26	0
272	451. Sort Characters By Frequency	흑화뉴비	24.02.07	40	0
271	49. Group Anagrams	흑화뉴비	24.02.06	33	0
270	931. Minimum Falling Path Sum	흑화뉴비	24.01.19	21	0
269	2125. Number of Laser Beams in a Bank	흑화뉴비	24.01.04	29	0
268	455. Assign Cookies	흑화뉴비	24.01.02	28	0
267	1155. Number of Dice Rolls With Target S	흑화뉴비	23.12.26	27	0
266	leetcode 풀기 vs 학교교재로 기초다지기 [1]	ㅇㅇ(223.39)	23.11.25	86	0
265	1630. Arithmetic Subarrays	흑화뉴비	23.11.23	30	0
264	1877. Minimize Maximum Pair Sum in Array	흑화뉴비	23.11.19	26	0
263	1269. Number of Ways to Stay in the Same	흑화뉴비	23.10.16	37	0
262	1095. Find in Mountain Array	흑화뉴비	23.10.13	37	0
261	2749. Minimum Operations to Make the Int	개발뉴비	23.06.26	36	0
260	2448. Minimum Cost to Make Array Equal	개발뉴비	23.06.21	40	0
249	갤주님 구현문제 잘 푸는 방법 좀요 [7]	ㅇㅇ(222.236)	23.04.08	132	1
248	오랜만에 오늘의 릿코드 한줄컷	개발뉴비	23.04.05	54	0
247	개강하니 귀신같이 정전갤됐네	ㅇㅇ(210.107)	23.03.31	44	0
246	1319. Number of Operations to Make Netwo	개발뉴비	23.03.23	42	0
245	958. Check Completeness of a Binary Tree	개발뉴비	23.03.15	44	0
244	129. Sum Root to Leaf Numbers	개발뉴비	23.03.14	32	0
242	101. Symmetric Tree	개발뉴비	23.03.13	38	0
241	382. Linked List Random Node	개발뉴비	23.03.11	27	0
240	142. Linked List Cycle II	개발뉴비	23.03.10	32	0
239	142. Linked List Cycle II	chromate00	23.03.09	33	0
238	875. Koko Eating Bananas	chromate00	23.03.08	28	0
237	875. Koko Eating Bananas	개발뉴비	23.03.08	41	0
236	2187. Minimum Time to Complete Trips	개발뉴비	23.03.08	36	0
235	2187. Minimum Time to Complete Trips	chromate00	23.03.07	23	0
234	1539. Kth Missing Positive Number	개발뉴비	23.03.06	34	0
233	1539. Kth Missing Positive Number	chromate00	23.03.06	22	0
232	1345. Jump Game IV	개발뉴비	23.03.05	34	0
231	2444. Count Subarrays With Fixed Bounds	ㅇㅇ(93.177)	23.03.04	29	0
230	2444. Count Subarrays With Fixed Bounds	ㅇㅇ(93.177)	23.03.04	26	0
229	28. Find the Index of the First Occurren	chromate00	23.03.03	32	0
228	8. Find the Index of the First Occurrenc	개발뉴비	23.03.03	38	0
	8. Find the Index of the First Occurrenc	ㅇㅇ(46.165)	23.03.03	30	0
226	443. String Compression	개발뉴비	23.03.02	33	0
225	912. Sort an Array	개발뉴비	23.03.01	41	0
224	912. Sort an Array	chromate00	23.03.01	32	0
223	임마들 개강했다고 문제 안풀고 빠져가지고... [2]	ㅇㅇ(218.234)	23.02.28	85	0
222	427. Construct Quad Tree	chromate00	23.02.27	24	0
221	427. Construct Quad Tree	개발뉴비	23.02.27	32	0
220	72. Edit Distance	chromate00	23.02.27	27	0
219	72. Edit Distance	개발뉴비	23.02.27	43	0
217	121. Best Time to Buy and Sell Stock	개발뉴비	23.02.25	29	0
216	121. Best Time to Buy and Sell Stock	이벤트	23.02.25	28	0
215	121. Best Time to Buy and Sell Stock	chromate00	23.02.25	30	0
214	1675. Minimize Deviation in Array	개발뉴비	23.02.25	27	0