PS 이야기

1) Knuth-Morris-Pratt Algorithm 2) Aho-Corasick Algorithm 1) Knuth-Morris-Pratt Algorithm KMP Algorithm은 패턴 $P$와 문자열 $S$가 있을 때, 문자열 $S$에 패턴 $P$가 부분문자열로 있는지, 혹은 몇 개 있는지 선형시간 $O(|S| + |P|)$에 확인하는 방법이다. 기본적인 아이디어는 실패 함수 f(i)에서 온다. 아래는 패턴 $P$가 "abracadabra" 일 때 실패 함수 값을 표로 나타낸 것이다. i 1 2 3 4 5 6 7 8 9 10 11 P a b r a c a d a b r a f 0 0 0 1 0 1 0 1 2 3 4 $P[i, j]$를 패턴 $P$의 $i$번째 문자부터 $j$번째 문자까지로 구성된..