KMP 접두사 함수

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

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

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

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

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

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

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

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

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

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

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

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

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