자료구조와 함께 배우는 알고리즘 입문 [파이썬] - 7장. 문자열 검색

문자열 검색: 어떤 문자열 안에 다른 문자열이 포함되어 있는지 검사하고, 만약 포함되어 있다면 어디에 위치하는지 찾아내는 것

7-1. 브루트 포스

• 맨 앞부터 시작하여 각 원소들을 비교 일치하지 않으면 패턴을 오른쪽으로 이동시키고 반복
• 이미 검사한 위치를 기억하지 못하므로 효율 x

def bf_match(txt: str, pat: str) -> int:
    """브루트 포스법으로 문자열 검색"""
    pt = 0  # txt(텍스트)를 따라가는 커서
    pp = 0  # pat(패턴)를 따라가는 커서

    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        else:
            pt = pt - pp + 1
            pp = 0

    return pt - pp if pp == len(pat) else -1

• 멤버십 연산자 in, not in 으로 포함되어 있는지 검색 가능, 위치는 모름
• find : str.find(sub[, start[, end]]) 포함되면 가장 작은 인덱스 반환, 아니면 -1 반환 start, end 생략 가능 슬라이스 표기에 따라 지정
  
• rfind: str.rfind(sub[, start[, end]]) 포함되면 가장 큰 인덱스 반환, 아니면 -1 반환 start, end 생략 가능 슬라이스 표기에 따라 지정
  
• index: str.index(sub[, start[, end]]) 포함되면 가장 작 인덱스 반환, 아니면 에러 start, end 생략 가능 슬라이스 표기에 따라 지정
  
• rindex: str.rindex(sub[, start[, end]]) 포함되면 가장 큰 인덱스 반환, 아니면 에러 start, end 생략 가능 슬라이스 표기에 따라 지정
  
• with:
  • str.startswith(sub[, start[, end]]) 문자열이 sub로 시작하면 True, 아니면 False
  • str.endswith(sub[, start[, end]]) 문자열이 sub로 끝나면 True, 아니면 False
  • start, end 생략 가능 슬라이스 표기에 따라 지정

---

7-2. KMP법

• 결과가 일치하지 않더라도 검사했던 결과를 버리지 않고 효율적으로 활용
• 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴 이동을 되도록 크게 하는 알고리즘
• 몇번째부터 다시 검색할지를 표로 만들어서 문제 해결
• 보이어-무어법 보다 성능면에서 낮아서 실제에서 별로 사용하지 않음

def kmp_match(txt: str, pat: str) -> int:
    """KMP법에 의한 문자열 검색"""
    pt = 1  # txt를 따라가는 커서
    pp = 0  # pat를 따라가는 커서
    skip = [0] * (len(pat) + 1)  # 건너뛰기 표

    # 건너뛰기 표 만들기
    skip[pt] = 0
    while pt != len(pat):
        if pat[pt] == pat[pp]:
            pt += 1
            pp += 1
            skip[pt] = pp
        elif pp == 0:
            pt += 1
            skip[pt] = pp
        else:
            pp = skip[pp]

    # 검색하기
    pt = pp = 0
    while pt != len(txt) and pp != len(pat):
        if txt[pt] == pat[pp]:
            pt += 1
            pp += 1
        elif pp == 0:
            pt += 1
        else:
            pp = skip[pp]

    return pt - pp if pp == len(pat) else -1

---

7-3. 보이어-무어법

• 패턴의 끝 문자에서 시작해서 앞쪽으로 검사 수행
• 포함되지 않으면 그 위치까지 건너뜀
• 보이어/무어법 알고리즘도 각각의 문자를 만났을 때 패턴을 이동할 크기를 저장하는 표(건너뛰기 표)를 미리 만들어 둘 필요가 있다. 패턴 문자열의 길이가 n일 때 이동할 크기(이동량)는 다음과 같이 결정한다.
  • 패턴에 포함되지 않는 문자를 만난 경우
    : 패턴 이동량이 곧 n이다.
  • 패턴에 포함되는 문자를 만난 경우
    : 마지막에 나오는 위치의 인덱스가 k이면 이동량은 n-k-1이다. 만약 같은 문자가 패턴 안에 중복해서 존재하지 않으면 패턴의 맨 끝 문자의 이동량은 n이다.
    ex) 'abac'의 'c'를 만나면 이동할 필요가 없으므로 이동량은 n이다.

def bm_match(txt, pat):
    skip = [None] * 256     # 건너뛰기 표
    
    # 건너뛰기 표 만들기
    for pt in range(256):
        skip[pt] = len(pat)
    for pt in range(len(pat)):
        skip[ord(pat[pt])] = len(pat) - pt - 1
     
    # 검색하기   
    while pt < len(txt):
        pp = len(pat) - 1
        while txt[pt] == pat[pp]:
            if pp == 0:
                return pt
            pt -= 1
            pp -= 1
        pt += skip[ord(txt[pt])] if skip[ord(txt[pt])] > len(pat) - pp \
                else len(pat) - pp
            
        return -1

---

문자열 검색 알고리즘의 시간 복잡도

• 브루트 포스: 시간 복잡도는 O(mn)이지만 일부러 꾸며 낸 패턴이 아니라면 O(n)이 된다고 알려져 있다. 단순하고 비효율적이지만 간단한 경우 빠르게 동작한다.
• KMP: 최악의 경우에도 O(n)이다. 다만 처리하기 복잡하고 패턴 안에 반복이 없으면 효율이 좋지 않다. 그러나 검색 과정에서 주목하는 곳을 앞으로 되돌릴 필요가 없으므로 파일을 차례로 읽어 들이면서 검색할 때 사용하면 좋다.
• 보이어/무어: 최악의 경우 O(n), 평균 O(n / m)이다. 배열을 1개가 아닌 2개로 알고리즘을 구현한다면 효율성이 떨어진다.

일반적으로 파이썬에서 문자열을 검색한다면 표준 라이브러리를 사용하는 것이 좋다.