문자열 매칭 알고리즘은 주어진 패턴 문자열과 대상 문자열에서 패턴이 일치하는 위치를 찾는 알고리즘입니다. 이 알고리즘은 문자열 검색, 텍스트 처리, 데이터베이스 검색 등에서 많이 사용됩니다.
1. 브루트 포스 알고리즘
가장 간단한 문자열 매칭 알고리즘은 브루트 포스 알고리즘입니다. 이 알고리즘은 패턴의 각 위치에서 대상 문자열과 일치 여부를 비교하는 방식으로 동작합니다. 일치하는 패턴이 발견되면 해당 위치를 반환하고, 일치하는 패턴이 없을 경우 -1을 반환합니다.
def brute_force(text, pattern):
n = len(text)
m = len(pattern)
for i in range(n - m + 1):
j = 0
while j < m and text[i + j] == pattern[j]:
j += 1
if j == m:
return i
return -1
2. KMP 알고리즘
KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 매칭을 위한 효율적인 알고리즘으로, 불필요한 비교를 줄여 시간 복잡도를 개선합니다. 이 알고리즘은 패턴 내에 일치하지 않는 문자가 나온 경우, 이전에 일치했던 부분을 이용해 다음 비교 위치를 결정합니다.
def kmp(text, pattern):
n = len(text)
m = len(pattern)
pi = get_pi(pattern)
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = pi[j - 1]
if text[i] == pattern[j]:
if j == m - 1:
return i - m + 1
else:
j += 1
return -1
def get_pi(pattern):
m = len(pattern)
pi = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = pi[j - 1]
if pattern[i] == pattern[j]:
j += 1
pi[i] = j
return pi
3. 보이어-무어 알고리즘
보이어-무어 알고리즘은 브루트 포스 알고리즘과 달리 오른쪽에서 왼쪽으로 비교해가며 일치하지 않는 문자가 나오면, 패턴을 이동시키는 방식으로 동작합니다. 이 알고리즘은 패턴의 오른쪽 끝에 있는 문자가 일치하지 않는 경우, 패턴의 이동 거리를 더 효율적으로 계산하여 시간을 단축시킵니다.
def boyer_moore(text, pattern):
n = len(text)
m = len(pattern)
skip = [m] * 256
for i in range(m - 1):
skip[ord(pattern[i])] = m - i - 1
i = m - 1
while i < n:
j = m - 1
while text[i] == pattern[j]:
if j == 0:
return i
i -= 1
j -= 1
i += max(skip[ord(text[i])], m - j)
return -1
위의 세 가지 알고리즘은 각각의 특징과 성능을 가지고 있으며, 사용하는 상황에 따라 선택할 수 있습니다. 브루트 포스 알고리즘은 가장 간단하지만, 패턴과 대상 문자열의 길이가 클 경우에는 성능이 저하될 수 있습니다. KMP 알고리즘은 중복된 비교를 최소화하여 성능을 향상시킬 수 있지만, 구현이 복잡할 수 있습니다. 보이어-무어 알고리즘은 오른쪽에서 왼쪽으로 비교하며 일치하지 않는 경우 패턴을 이동시키기 때문에 평균적으로 더 효율적입니다.
더 많은 문자열 매칭 알고리즘을 알고 싶다면 링크를 참고해주세요.