패턴매칭 알고리즘

1. 보이어무어

시간복잡도: 최악 O(m*n) but 빠를때는, 매우 빠르다.

일반적인 상용 시스템에서 사용중

패턴의 마지막 요소, 즉 오른쪽 인덱스를 기준점으로!

해당 문자열이 패턴에 있다면, 그 인덱스까지 skip

없다면, 완전히 뒤로 (패턴 길이만큼 skip)

2. KMP 알고리즘

탐색하다가, 불일치를 만나면 1칸 jump가 아닌 여러칸 점프!
그 점프 구간을 어떻게 정하고 구할 것인데? 에 관한 알고리즘

시간복잡도: O(n+m)

Knuth, Morris, Pratt 3명의 합작 알고리즘

탐색 문자열의 앞 = 접두사
탐색 문자열의 뒤 = 접미사

핵심! 접두사 == 접미사가 같아야 jump 할 수 있다.