[python] 문자열매칭. KMP 알고리즘 (백준16916, 백준1786)

단어검색 (문자열매칭) 요구사항 

- 워드안에서 Ctrl+F하는 것 처럼, 검색한 단어들이 있는 모든 위치를 전부 알려줘! 

- 단어사전에 단어가 수만개, 문서길이가 수천개

- 문서는 띄어쓰기가 없거나 마구잡이로 된 상황

- 문서안에 검색할 단어가 여러번 출현해서 문서전체를 훑어야한다.

 

1. find() 

문자열의 위치를 반환하지만, 단어가 문자열내에서 나타나는 첫위치 하나만 리턴한다.

그래서 검색할 단어가 여러번 나타날 경우 처리할 수가 없다

2. 정규식 라이브러리(re) 사용

re.match(), re.finditer() 으로 매칭되는 좌표를 전부 리스트로 반환해준다.  

하지만, 데이터의 양이 많아지게 될 경우 시간이 오래걸리는 문제점이 있다.

3. 문자열매칭 알고리즘

위와같은 제한사항으로 인해 문자열매칭 알고리즘을 사용하면, 빠르게 해결할 수 있다 

 

문자열매칭에 사용되는 알고리즘

1. Naive Matching (원시적인 매칭) - O(mn)O(mn)

2. Automata Algorithm (오토마타를 이용한 매칭) - Θ(n+|∑|m)Θ(n+|∑|m)

3. Rabin-Karp Algorithm (라빈-카프 알고리즘) - Θ(n)Θ(n)

4. Knuth-Morris-Pratt(KMP) Algorithm (KMP알고리즘) - Θ(n)Θ(n)

5. Boyer-Moore Algorithm (보이어-무어 알고리즘) - Θ(n)Θ(n) Worst Case: Θ(nm)

 

KMP알고리즘 

문자열과 패턴이 주어질때, 문자열 안에서 주어진 패턴을 찾아내는 알고리즘

보통 시간복잡도는 문자열길이*패턴길이로 O(n^2)인데, KMP알고리즘은 O(n)으로 줄어든다.  

 

패턴에서 접두사와 접미사가 같은 최대개수를 활용하는 것이 핵심이다. 

그래서 접두사를 미리 뽑아놓는 get_pi(패턴)함수를 사전에 구해야한다.

def get_pi(P):
    m = len(P)
    pi = [0 for i in range(m)]
    idx = 0
    for i in range(1, m):
        while idx > 0 and P[i] != P[idx]: #idx가 0이거나, i와idx의 문자열이 같을때까지 반복
            idx = pi[idx - 1]

        if P[i] == P[idx]: #i와 idx가 같을경우 idx증가
            idx += 1
            pi[i] = idx #i번쨰의 값으로 idx 저장

    return pi

이 함수는 패턴의 길이만큼 접미사가 같은 최대수를 반환한다.

예를 들어 abacaba 패턴일 경우 아래와 같은 경우 때문에 [0,0,1,0,1,2,3]이 된다.

 

그리고 나서 그걸 이용해서 본격적으로 패턴을 확인한다.

def kmp(S, P):
    n = len(S)
    m = len(P)

    pi = get_pi(P)
    print(pi)
    idx = 0
    for i in range(0, n):
        while idx > 0 and S[i] != P[idx]:
            idx = pi[idx - 1]
        if S[i] == P[idx]:
            if idx == m - 1:
                return 1
            else:
                idx += 1
    return 0

 

 

엉엉 너무 어렵자나ㅠㅠ

 

KMP알고리즘을 이용한 백준문제 

1786. 찾기 https://www.acmicpc.net/problem/1786

16916. 부분문자열 https://www.acmicpc.net/problem/16916

 

 

 

출처 

https://hooongs.tistory.com/304

[Algorithm] KMP 알고리즘 with Python

https://ohdowon064.tistory.com/222

Algorithm. 문자열 - 문자열 매칭