[CS공부] 7. 문자열 검색

깃허브 정리본

용어

• brute force method(브루트포스법) = 단순법: 선형 검색의 확장판으로, 문자열의 첫 문자부터 순차적으로 검색해 나가는 것
  => 이미 검사한 위치를 기억하지 못해 효율이 좋지 않음
  => O(n)의 시간 복잡도를 가짐

• KMP법: 텍스트와 패턴안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구해 패턴의 이동을 되도록 크게하는 알고리즘
  => 검사했던 결과를 버리지 않고 활용해 효율적인 문자열 검색 알고리즘
  => 몇번째 문자부터 다시 검색할지 미리 표로 만들어두고 활용
  => but 보이어-무어법에 비해 알고리즘은 복잡하고 성능은 모자라 실제로 잘 쓰이지 않음
  => 최악의 경우 O(n)의 시간 복잡도

• 보이어-무어법: 패턴의 끝문자부터 앞쪽을 향해 검사를 수행하며, 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동
  => 실제 문자열 검색에서 널리 사용되는 알고리즘
  => 최악의 경우 O(n)의 시간복잡도, 평균 O(n/m)

실습

브루트 포스법

def brute_force_search(txt: str, ptn: str) -> int:
    txt_p = 0
    ptn_p = 0

    while txt_p != len(txt) and ptn_p != len(ptn):
        if txt[txt_p] == ptn[ptn_p]:
            txt_p += 1
            ptn_p += 1
        else:
            txt_p = txt_p - ptn_p + 1
            ptn_p = 0
    
    return txt_p - ptn_p if ptn_p == len(ptn) else -1

print(brute_force_search("abcdef1234", "cd"))
print(brute_force_search("abcdef1234", "f1"))
print(brute_force_search("abcdef1234", "ac"))
print(brute_force_search("abcdef1234", "def123"))


# 실행결과 ==========================================
2
5
-1
3

KMP법

def kmp_search(txt: str, ptn: str) -> int:
    txt_p = 1
    ptn_p = 0
    skip_arr = [0] * (len(ptn)+1)

    while txt_p != len(ptn):
        if ptn[txt_p] == ptn[ptn_p]:
            txt_p += 1
            ptn_p += 1
            skip_arr[txt_p] = ptn_p
        elif ptn_p == 0:
            txt_p += 1
            skip_arr[txt_p] = ptn_p
        else:
            ptn_p = skip_arr[ptn_p]
    
    txt_p = 0
    ptn_p = 0

    while txt_p != len(txt) and ptn_p != len(ptn):
        if txt[txt_p] == ptn[ptn_p]:
            txt_p += 1
            ptn_p += 1
        elif ptn_p == 0:
            txt_p += 1
        else:
            ptn_p = skip_arr[ptn_p]
    
    return txt_p - ptn_p if ptn_p == len(ptn) else -1


print(kmp_search("abcdef1234", "cd"))
print(kmp_search("abcdef1234", "f1"))
print(kmp_search("abcdef1234", "ac"))
print(kmp_search("abcdef1234", "def123"))


# 실행결과 ==========================================
2
5
-1
3

보이어 무어법

def b_m_search(txt: str, ptn: str) -> int:
    skip_arr = [0] * 256

    for txt_p in range(256):
        skip_arr[txt_p] = len(ptn)
    for txt_p in range(len(ptn)):
        skip_arr[ord(ptn[txt_p])] = len(ptn) - txt_p - 1
    
    while txt_p < len(txt):
        ptn_p = len(ptn) - 1
        while txt[txt_p] == ptn[ptn_p]:
            if ptn_p == 0:
                return txt_p
            txt_p -= 1
            ptn_p -= 1
        txt_p += max(skip_arr[ord(txt[txt_p])], len(ptn) - ptn_p)

    return -1


print(b_m_search("abcdef1234", "cd"))
print(b_m_search("abcdef1234", "f1"))
print(b_m_search("abcdef1234", "ac"))
print(b_m_search("abcdef1234", "def123"))


# 실행결과 ==========================================
2
5
-1
3

정리

문자열 검색 알고리즘은 보이어-무어법이라는
가장 강력한 도구가 있어 문제를 풀때도
이걸 주로 활용할 듯 하다.

교재에 있는 코드대로 작성해봤는데,
내 손에 익는 방식대로 다시 작성해봐야겠다.