[자료구조와 함께 배우는 알고리즘][정렬 알고리즘] - 문자열 검색(KMP법)

1. KMP법이란?

브루트 포스법은 일치하지 않는 문자를 만나면 이전 단계에서 검사했던 결과를 버리고 패턴의 첫 문자부터 다시 검사를 수행한다. 하지만 KMP법은 검사했던 결과를 버리지 않고 효율적으로 활용하는 알고리즘이다.

 

텍스트와 패턴 안에서 겹치는 문자열을 찾아내 검사를 다시 시작할 위치를 구하고 패턴의 이동을 되도록이면 크게 하는 알고리즘이 KMP 알고리즘이다.

 

 

2. KMP 알고리즘 구현 코드

# KMP법으로 문자열 검색하기

def kmp(txt, pat):

    pt = 1 # 텍스트를 따라가는 커서
    pp = 0 # 패턴을 따라가는 커서

    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

s1 = input("텍스트를 입력하세요.: ")
s2 = input("패턴을 입력하세요.")

idx = kmp(s1,s2)

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

 

 

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

	브루트 포스	KMP	보이어 · 무어
문자열 검색 알고리즘의 시간 복잡도	O(mn) - 일반적 경우 O(n) - 일부러 꾸며 낸 패턴이 아닌 경우	O(n) - 최악의 경우에도 이에 속하며 처리하기가 복잡하고 패턴 안에 반복이 없으면 효율성이 떨어지기 때문에 파일을 차례대로 읽어 들이며 검색하는 경우에 사용하면 좋다.	O(n) - 최악의 경우 O( n / m ) - 평균 배열을 만드는 데 복잡한 처리 과정이 필요해서 효율성이 덜어진다. 이때 배열을 1개를 만들어 사용하는 경우는 충분히 빠르지만 2개를 만들어 사용하는 경우엔 매우 효율성이 떨어진다.