1. KMP란?

• 문자열 검색을 매우 빠르게 해 주는 알고리즘
• made by 3명의 개발자 : Knuth-Morris-Pratt
  • James H. Morris가 먼저 생각했고
  • 몇 주 후, (면식이 없는) Donald Knuth가 “오토마타 이론”에서 이와 비슷한 알고리즘을 발견하고
  • Morris와 Vaughan Pratt가 1970년에 기술 보고서를 발표했고
  • 세 사람은 1977년 이 알고리즘을 공동으로 발표했다.

⇒ 즉, 특정 패턴이 주어졌을 때 전체 문자열을 빠르게 검색하여 그 패턴이 어디에 등장하는지 찾아주는 알고리즘

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

→ 완전탐색은..O(nm)

2. KMP의 원리

1) 주어진 패턴에 대해 skip 배열을 만든다.

`skip`은 패턴의 각 인덱스마다 접두사와 접미사가 동일한 갯수

2) skip 배열을 활용하여 패턴의 등장 위치를 찾는다. (빠르게)

※ 먼저 알아야 하는 것!

• 1) 접두사(prefix) / 접미사(suffix)
• 2) pi 배열 (퀴즈 코드는 skip으로 사용)

자, 드가자-!

kmp_match.py 코드를 실행할 때,
s1 = "abcabgabcaabcabcabgabcaef"
s2 = "abcabgabcae"
가 입력으로 주어지면
skip 배열과 count 값이 어떻게 될 지 맞춰 보시면 됩니다.
kmp_match.py는 책에 있는 걸 그대로 옮겨 오되, print 문만 추가했습니다.