문자열 검색

브루트 포스법

패턴을 한칸씩 움직여서 텍스트와 일치할때 까지 움직인다. 텍스트 인덱스 2 3 4 의 원소와 일치하여 검색에 성공한다.

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#패턴의 모든 문자가 일치하여 pp가 패턴의 길이와 같아진다면, 일치하는 부분의 시작 인덱스 반환, 아니면 -1

if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')  # 텍스트용 문자열
    s2 = input('패턴을 입력하세요.: ')    # 패턴용 문자열

    idx = bf_match(s1, s2)  # 문자열 s1~s2를 브루트 포스법으로 검색

    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx + 1)}번째 문자에서 일치합니다.')

KMP법

kmp법은 검사했던 결과를 버리지 않고 효율적으로 활용한다.

한칸 움직여서 패턴의 앞쪽부터 차례로 수행하면 패턴의 마지막 문자 'D'가 텍스트의 'X'와 일치하지 않는다.

AB를 위아래로 나란히 놓고 패턴을 한번에 오른쪽으로 3칸 밀어서 세번째 문자 'C'부터 검사를 시작한다. 

kmp법은 텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하여 패턴 이동을 되도록 크게 한다.

KMP 표 만들기

패턴과 텍스트를 서로 겹치도록 맞추는게 아니라 패턴끼리 서로 겹치도록 맞추고 검사를 시작할 곳을 계산한다.

1) 2개를 위아래로 놓고 오른쪽으로 한칸 밀어 첫문자부터 다시 검사한다. 문자가 일치하지 않으므로 0을 입력한다.

A	B	C	A	B	D
-	0

2) 한칸 더 오른쪽으로 밀고 문자가 일치하지 않으므로 0을 입력한다.

A	B	C	A	B	D
-	0	0

 

3) A와 B는 다시 시작하는 값을 표에서 각각 1과 2로 작성한다.

A	B	C	A	B	D
-	0	0	1	2	0

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 #일치하는 위치 찾으면 그 위치의 인덱스 반환, 없으면 -1 반환

if __name__ == '__main__':
    s1 = input('텍스트를 입력하세요.: ')  # 텍스트용 문자열
    s2 = input('패턴을 입력하세요.: ')    # 패턴용 문자열

    idx = kmp_match(s1, s2)  # 문자열 s1~s2를 KMP법으로 검색

    if idx == -1:
        print('텍스트 안에 패턴이 존재하지 않습니다.')
    else:
        print(f'{(idx + 1)}번째 문자에서 일치합니다.')

보이어 무어법

보이어 무어법은 패턴 끝문자에서 시작하여 앞쪽을 향해 검사를 수행한다.

하나씩 움직이는 과정을 생략하고 마지막문자가 일치하도록 오른쪽으로 한번에 5칸을 민다. 맨끝 부터 하나씩 비교하여 일치하는 문자를 검색한다.

패턴이 포함되지 않는 문자를 만나면-> n만큼 패턴을 이동시킨다.

패턴이 포함되는 문자를 만난 경우-> 마지막에 나오는 위치의 인덱스가 k면 이동량은 n-k-1이다. 같은 문자가 패턴 안에 중복해서 존재하지 않으면 패턴의 맨 끝 문자의 이동량은 n이다. 예를 들어 'ABAC' 의 'C'를 만나면 이동할 필요가 없으므로 이동량은 n이다.

def bm_match(txt: str, pat: str) -> int:
    """보이어 무어법에 의한 문자열 검색"""
    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 \ #패턴과 불일치가 발생한 위치까지의 거리(len(part)-pp)
              else len(pat) - pp

    return -1

시간복잡도

브루트 포스법 -> O(n)

KMP법 ->  kmp의 시간복잡도는 최악의 경우에도 O(n) 이다. 

보이어 무어법-> 최악의 경우에는 O(n)이고 평균 O(n/m) 이다.