🚀 What I Will Learn

• 구현하기 쉬운 문자열 매칭 알고리즘 원리에 대해 이해하기
• 효율적인 문자열 매칭 알고리즘인 KMP 알고리즘에 대해 이해하기

KMP 알고리즘은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다

---

KMP 문자열 매칭

1️⃣ 단순 비교 문자열 매칭

• 단순 비교 문자열 매칭 알고리즘은 두 문자열을 처음부터 끝까지 계속 비교하는 알고리즘이다
• 단순 비교 문자열 매칭 알고리즘은 𝑂(𝑁𝑀)의 시간 복잡도를 가진다

시간복잡도: 문제를 해결하는데 걸리는 시간과 입력의 함수 관계.
컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것을 의미

✔️ 단순 비교 문자열 매칭 원리

• 문자열 A에서 문자열 B를 찾는 과정

문자열 A	'ABCDEFG'
문자열 B	'EF'

---

2️⃣ KMP 문자열 매칭

• 단순 비교 문자열 매칭 알고리즘은 𝑂(𝑁𝑀)의 시간 복잡도로 상당히 비효율적이다
• KMP 문자열 매칭 알고리즘을 활용하면 𝑂(𝑁 + 𝑀)의 시간 복잡도로 문제를 해결할 수 있다

✔️ KMP 문자열 매칭 원리

KMP 알고리즘은 접두사와 접미사를 활용해 빠르게 문자열 매칭을 수행하는 알고리즘이다

1) 접두사와 접미사

• 특정한 부모 문자열에서 찾고자 하는 패턴 (Pattern) 문자열이 abacdab라고 가정.
  • 이 때, 각 길이에 따른 접두사와 접미사가 일치하는 최대 길이를 구한다

2) 테이블 만들기

• j=0,i=1로 설정하고 테이블 만들기를 진행

  • i는 한 칸씩 이동

  

• pattern[j]와 pattern[i]가 일치하는지 반복적으로 확인.

  • 일치하는 경우, j에 1을 더한 뒤에 j의 인덱스를 table[i]에 삽입

  

• 불일치하는 경우 j를 마지막으로 일치했던 순간까지의 인덱스로 이동해 다시 검사.

  • 마지막으로 일치했던 순간은 table[j – 1]

  

• 마지막으로 일치했던 순간은 table[j – 1]으로 이동해서 검사했을 때에도 일치하지 않을 경우 무시 ➡️ 0

  

• 이러한 과정을 마지막 문자까지 반복

3) 문자열 매칭 진행

• 문자열 매칭을 진행할 때에도 불일치하는 경우 j를 마지막으로 일치했던 순간까지의 인덱스로 이동해 다시 검사.
  • 마지막으로 일치했던 순간은 table[j – 1]

---

✨ tl;dr

• KMP 문자열 매칭 알고리즘은 𝑂(𝑁 + 𝑀)의 시간 복잡도를 가진다