14일차 강의 (30강)

30강 (KMP)

드물게 나옴

 

S[a:b] = "S[a]S[a+1]...S[b-1]"

lSl는 S의 길이

접두사 = 문자열의 첫 문자를 포함하는 연속한 문자열

접미사 = 문자열의 끝 문자를 포함하는 연속한 문자열

 

패턴 매칭 문제

 

실패함수

KMP : 패턴 매칭 문제를 O(|A| + |B|)에 해결할 수 있는 기적의 알고리즘

굉장히 헷갈림

먼저 KMP에서 쓰이는 실패 함수를 알면 KMP를 이해하는데 도움이 됨

 

실패함수 F(x) : 문자열 S[0:x+1]에서 접두사와 접미사가 일치하는 최대 길이

 

KMP