0Pricing
Coding Interview Prep · 강의

KMP 접두사 함수

O(n + m)에 패턴을 찾습니다

KMP 접두사 함수은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

패턴 매칭 문제

긴 문자열 안에서 짧은 패턴이 나타나는 위치를 찾고 싶을 때가 있습니다. 순진한 비교는 느리므로, 대회에서는 더 똑똑한 탐색을 사용합니다. 🔍

순진한 탐색이 느린 이유

모든 위치에서 패턴을 비교하면 실행 시간이 O(n*m)까지 걸릴 수 있습니다. 입력이 크면 제한 시간을 조용히 초과하게 됩니다.

접두사 함수 소개

prefix function은 각 위치에서 접두사이면서 동시에 접미사인 가장 긴 진부분 문자열의 길이를 측정합니다. KMP의 핵심입니다.

진접두사와 진접미사

진접두사나 진접미사는 문자열 전체와 같은 경우를 제외한 접두사나 접미사입니다. ababa에서는 가장 긴 일치 쌍의 길이가 3이며, 그 문자열은 aba입니다.

pi[i]에 저장되는 값

값은 pi라는 배열에 저장합니다. 여기서 pi[i]는 인덱스 i에서 끝나는 부분 문자열의 가장 긴 접두사와 접미사의 일치 길이입니다.

한 번의 순회로 pi 만들기

pi는 왼쪽에서 오른쪽으로 만들며, 처음부터 다시 비교하는 대신 앞에서 계산한 값을 재사용합니다. 이 재사용이 핵심 요령입니다.

def prefix_function(s):
    pi = [0] * len(s)
    return pi

대체 반복문

문자가 일치하지 않으면 0으로 초기화하는 대신 pi[k-1]로 되돌아갑니다. 그러면 같은 작업을 다시 하지 않아도 됩니다.

while k > 0 and s[i] != s[k]:
    k = pi[k - 1]

일치 구간 늘리기

현재 문자들이 일치하면 길이를 1 늘리고 그 값을 기록합니다. 길이가 0인 상태에서 불일치하면 계속 0으로 둡니다.

if s[i] == s[k]:
    k += 1
pi[i] = k

이 요령으로 탐색하기

문자열에서 패턴을 찾으려면 둘을 pattern + sep + text 형태로 이어 붙입니다. 패턴 길이와 같은 pi 값이 있으면 전체 패턴이 일치한 것입니다.

combined = pattern + chr(0) + text
pi = prefix_function(combined)

구분자가 중요한 이유

구분자는 두 문자열 어느 쪽에도 없는 기호입니다. 구분자가 있으면 이어 붙인 경계를 넘어 일치하는 일이 방지되어 잘못된 결과를 피할 수 있습니다.

선형 시간의 이점

만들기와 탐색 모두 O(n + m)에 수행됩니다. 각 문자를 한 번씩 처리하므로 KMP는 매우 큰 대회 입력에도 대응할 수 있습니다.

빠른 확인

접두사 함수가 무엇을 기록하는지 제대로 이해했는지 확인해 보십시오.

복습: KMP 한눈에 보기

prefix function을 배웠습니다. pi를 한 번 만들고, 불일치하면 되돌아가며, 선형 시간에 탐색합니다. 이것이 KMP의 핵심입니다. 🎯

자주 묻는 질문

“KMP 접두사 함수” 강의는 무료인가요?

네 — “KMP 접두사 함수” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

“KMP 접두사 함수”에서 뭘 배우나요?

O(n + m)에 패턴을 찾습니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.

Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.

“KMP 접두사 함수” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

이 강의의 모든 강의

  1. KMP 접두사 함수
  2. 다항식 문자열 해싱
  3. 패턴 검색을 위한 Z 함수
  4. 접두사 조회를 위한 트라이
← Coding Interview Prep(으)로 돌아가기