Knuth-Morris-Pratt (1) 썸네일형 리스트형 87. Failure Function & Knuth-Morris-Pratt 앞선 글에서 문자열의 표현에 관한 내용들을 다루었고, 이제부터는 문자열의 검색에 대한 내용을 다룬다. 본격적인 내용을 설명하기에 앞서 용어를 정리한다. 어떤 문자열의 부분 문자열(Substring)은 문자열의 앞과 뒤에서 각각 $0$개 이상의 문자를 제거한 다음 남는 문자열을 의미한다. 이 글에서는 문자열 $s$의 부분 문자열을 $s[i, j]$로 표기하며, 이는 $s$의 $i$번째 ~ $j$번째 문자로 이루어진 부분 문자열이라는 뜻이다. 문자열의 인덱스는 0-based이다. 문자열의 접두사(Prefix)는 문자열의 뒤에서 $0$개 이상의 문자를 제거한 다음 남는 문자열을 의미한다. 문자열의 접미사(Suffix)는 문자열의 앞에서 $0$개 이상의 문자를 제거한 다음 남는 문자열을 의미한다. 문자열 $s$.. 이전 1 다음
