[알고리즘] 문자열 패턴 매칭

패턴 매칭에 사용되는 알고리즘

• 고지식한 패턴 검색 알고리즘(=Brute Force)
• 카프-라빈 알고리즘
• KMP 알고리즘
• 보이어-무어 알고리즘

---

고지식한 패턴 검색 (Brute Force)

• 문자열을 처음부터 끝까지 차례대로 순회, 패턴 내의 문자들을 일일이 비교
• 텍스트에서 패턴이 존재하는 모든 위치를 찾는 문제
• 시간복잡도 : O(MN)
  M: 패턴의 길이, N: 텍스트의 길이
  최악의 경우 텍스트의 모든 위치에 대해 패턴을 비교해야 함

패턴 매칭 알고리즘의 중요 포인트

• 일치하는 경우 ( t[i] == p[j] )
  • i, j를 증가시켜서 다음 문자를 비교
• 불일치하는 경우
  • 다음 매칭의 시작위치로 i, j 값을 설정

※ 자주 사용되는 대치어

	텍스트	패턴
기본	t	p
인덱스	i	j
길이	m	n

---

KMP 알고리즘

• 불일치가 발생한 텍스트 요소 앞부분에 어떤 문자가 있는지 알고 있는 것을 활용,
  불일치가 발생한 앞 부분에 대하여 다시 비교하지 않고 매칭을 수행하는 방법
• 텍스트와 패턴 사이의 요소를 비교하면서
  패턴의 접두어, 텍스트의 접미어를 계산해둔다
  • 현재 텍스트와 패턴이 일치하지 않을 때, 이후에 비교를 할 위치를 찾기 위함
  • BF방식에서 불필요한 계산을 하지 않고 Jump가 가능
• 시간복잡도 : O(M+N)

---

보이어-무어 알고리즘

• 패턴의 오른쪽에서 왼쪽으로 비교
• 대부분의 사용 소프트웨어에서 사용하고 있는 알고리즘
• 시간복잡도 : O(MN)
• 보이어-무어-호스풀 알고리즘이라는 간단한 버전의 알고리즘이 있다
• 텍스트 문자를 다 보지 않아도 된다는 장점이 있따.

---

비교

• 찾으려고 하는 문자열 패턴의 길이 m, 총 문자열 길이 n
• 브루트 포스 알고리즘 : O(MN)
• KMP 알고리즘 : O(N)  *일반적으로 좋음
• 보이어 무어 알고리즘 : O(MN)