문자열 패턴 매칭

1. 고지식한 패턴 검색 알고리즘
   완전탐색, O(NxM)

2. 라빈-카프 알고리즘
   해시 값 함수를 이용, 슬라이딩 윈도우, O(1)x(N-M+1)

3. 보이어-무어 알고리즘
   끝에서부터 문자열을 비교, 뒤로 얼마나 건너뛸지를 미리 skip배열에 저장한다. O(N/M)

4. KMP 알고리즘
   앞에서부터 문자열을 비교, 유의미한 위치로 이동하기 위한 부분일치 테이블을 미리 구한다.

KMP 알고리즘

패턴 매칭 문제를 O(N+M)에 해결할 수 있는 알고리즘

부분일치 테이블 배열 : 매칭이 실패했을 때 패턴 포인터가 돌아갈 곳을 계산
-> 맨 앞부터 해당 인덱스까지 부분문자열 중 접두사와 접미사가 일치하는 최대 길이를 계산

부분일치 테이블 배열

부분일치 테이블 배열에서 구해놓았던 배열의 값을 이용할 수 있다.
배열을 PI라고 선언하면, PI[i]는 최대 PI[i-1]+1이므로

• 만약 T[i]와 T[i-1], 두 글자가 일치한다면 PI[i] = PI[i]+1로 확정지을 수 있다.
• 일치하지 않는다면, 겹치는 구간을 그대로 살려 문자열을 밀어준 후 마지막 글자를 비교한다
  - 문자열을 밀어야 되는 인덱스는 j = PI[j-1]로 바뀐다.