반응형 Matching1 [자료구조] KMP(Knuth-Morris-Pratt) Algorithm KMP 알고리즘은 문자열 내에서 특정 패턴을 엄청나게 빠르게 찾아주는 알고리즘입니다. 해당 패턴의 위치를 빠르게 알 수 있지요. KMP알고리즘은 이전 포스팅의 마지막에 다루었던 패턴을 찾는 방법처럼 스트링과 패턴의 불일치가 발생했을 때 최대한 중복된 연산을 피하면서 문자열과 비교할 수 있도록 합니다. 이렇게 하기 위해서는 먼저 얼마나 중복연산을 피할것인지 판단하기 위한 값들이 필요합니다. 이를 failture function이라고 한다. failure function은 패턴문자열의 접두사와 접미사의 일치하는 부분을 계산하고 이를 fail 배열에 저장합니다. fail 배열의 첫 번째 인덱스의 값은 -1로 설정합니다. 인덱스의 의미는 현재 패턴의 문자가 패턴의 첫문자부터 #번째 문자까지 일치한다는 것을 말합.. 2024. 4. 14. 이전 1 다음 반응형
