문자열 알고리즘

N 길이의 문장에서 M 길이의 패턴을 찾는다고 생각할 때 다음과 같이 3가지 방법이 있다.

1. Brute-Force 탐색

• 가장 단순한 탐색 방법이다.
• O(MN)의 시간복잡도를 갖는다.

word = input()
sentence = input()
len1 = len(word)
len2 = len(sentence)
ans = 0
for i in range(len2 - len1 + 1):
    match = True
    for j in range(len1):
        if word[j] != sentence[i + j]:
            match = False
            break
    if match:
        ans += 1
print(ans)

2. KMP 알고리즘

• 불일치하더라도 탐색했던 정보를 활용하는 방법이다.
• 불일치 얼마나 건너뛰어야 할지(skip) 기록해놓은 pi 배열을 만들어서 활용한다.
• 패턴의 왼쪽에서 오른쪽으로 비교한다.
• O(M + N)의 시간 복잡도를 갖는다.

M = 0
N = 0


def getPi(p):
    pi = [0] * M
    cnt = 0  # 일치하는 문자 개수
    for i in range(1, M):
        while cnt > 0 and p[i] != p[cnt]:  # 일치하지 않으면 계속 건너뜀
            cnt = pi[cnt - 1]
        if p[i] == p[cnt]:
            cnt = cnt + 1
            pi[i] = cnt
    return pi


p = input()
s = input()
M = len(p)
N = len(s)
pi = getPi(p)
cnt = 0
match = 0
for i in range(N):
    while cnt > 0 and s[i] != p[cnt]:  # 일치하지 않으면 계속 건너뜀
        cnt = pi[cnt - 1]
    if s[i] == p[cnt]:
        cnt = cnt + 1
        if cnt == M:
            match = 1
            break

print(match)

3. 보이어-무어 알고리즘

• 패턴의 끝부분부터 비교한다.
• 끝부분이 앞부분보다 불일치 확률이 높아 실용적이다.
• 상용 제품에서 가장 많이 쓰이는 문자열 알고리즘이다.
• 일반적으로 O(N) 이하의 시간복잡도이지만, 최악의 경우 O(MN) 시간복잡도를 갖는다.
• 평균적으로 KMP 알고리즘보다 우수한 성능을 가진다.