12 / 16강

문자열에서 패턴 찾기

문서에서 단어를 찾으려면 패턴이 연속으로 등장하는 위치를 찾아야 합니다. 8강의 LCS처럼 중간 글자를 건너뛰어서는 안 됩니다.

가장 단순한 방법

패턴을 놓을 수 있는 시작 위치를 하나씩 고르고, 글자를 앞에서부터 비교합니다.

def find_pattern(text, pattern):
    if not pattern:
        return 0
    for start in range(len(text) - len(pattern) + 1):
        matched = True
        for offset in range(len(pattern)):
            if text[start + offset] != pattern[offset]:
                matched = False
                break
        if matched:
            return start
    return -1

print(find_pattern("ababc", "abc"))

출력은 2입니다. 인덱스는 0부터 셉니다. 빈 패턴은 0번 위치에서 찾은 것으로 정했습니다. 패턴이 본문보다 길면 후보 위치가 없어 -1을 반환합니다.

본문 길이가 n, 패턴 길이가 m일 때, 시작 위치마다 최대 m글자를 비교하므로 최악의 시간은 O(nm)입니다. aaaaab에서 aaab를 찾을 때처럼 비슷한 부분을 반복해서 읽을 수 있습니다.

KMP는 실패한 비교도 활용합니다

KMP는 패턴의 앞부분과 뒷부분이 얼마나 겹치는지 미리 기록합니다. 예를 들어 abab는 앞의 ab와 뒤의 ab가 같습니다. abab까지 맞춘 뒤 실패했다면, 이미 맞았던 끝의 ab를 다음 후보의 시작으로 활용할 수 있습니다.

이 겹침 정보로 본문 위치를 뒤로 돌리지 않고 비교를 이어갑니다. 패턴 준비에 O(m), 본문 탐색에 O(n)이 들어 전체 O(n+m)입니다. 어디로 돌아갈지를 기록한 표를 잘 만드는 것이 핵심입니다.

다른 방법도 전제를 봅니다

• 라빈-카프: 구간의 해시를 비교합니다. 해시가 같아도 충돌할 수 있으므로 실제 글자 비교가 필요합니다.
• 보이어-무어: 패턴 뒤쪽부터 비교하고 불일치 정보를 이용해 건너뜁니다. 구현과 사용하는 규칙에 따라 시간 보장이 달라집니다.
• 실제 코드에서 단순 검색이 목적이면 언어가 제공하는 검색 함수를 먼저 검토합니다.

확인 문제

본문 aaaa에서 패턴 aa가 나타나는 위치를 모두 구하면 몇 개인가요? 찾은 뒤 패턴 길이만큼 건너뛰어도 될까요?