오토마타1 KMP 그림 그리면서 구현 KMP의 Motivation이 무엇인지는 다른 곳에서 쉽게 찾아볼 수 있으니 여기에 굳이 설명을 적지는 않는다. KMP의 까다로운 점은 저 Motivation을 다 알아도 수많은 edge case들 때문에 구현하기가 상당히 까다롭다는 것이다. 유한 오토마타의 개념을 알고 있으면 KMP를 상당히 직관적으로 구현할 수 있다. 일단 ABABCABAC에 대응되는 실패 함수 배열을 살펴보자. A B A B C A B A C pi 0 0 1 2 0 1 2 3 0 실패 함수 := 문자열 s[0:i] 2개를 얼마나 겹치게 놓을 수 있느냐를 숫자로 나타낸 값. 예) i = 7일 때 문자열은 ABABCABA인데 이걸 카피 떠서 하나 더 만들면 ABABCABA ABABCABA임. 그런데 앞 문자열의 뒤 3개랑 뒤 문자열의 .. 2022. 11. 5. 이전 1 다음
