[python] 백준 - 16916. 부분 문자열

🤔문제 해결

• G4 | 문자열, KMP

딱 봐도 너무 쉽지만 G5니까…. 다른 방법으로 풀어야 한다고 생각했다.
들어는 봤어도 한 번도 써본 적 없는 KMP 알고리즘을 써야 문제를 해결할 수 있다.

KMP를 쓰면 브루트포스로 문자열 탐색하는 것보다 아주 빠르다. O(M+N)
한 시간 넘게 찾아가면서 공부했지만 설명하기는 너무 어렵다. 이해가 잘 안 된다. 나중에 한 번 더 봐야겠다.

대충 말해보자면
비슷한 패턴을 기억해뒀다가 패턴을 만나면 점프... (무슨 말인지 모르겠다)
어째 됐든 이 알고리즘은 많이 쓰이진 않지만, 적당히 알아만 두면 좋을 거 같다.

 

💻소스 코드

def kmp_match(txt: str, pat: str) -> int:
    # 스킵테이블 만들기
    def make_skip_table(skip: list):
        pt = 1  # txt를 따라가는 인덱스
        pp = 0  # pat를 따라가는 인덱스
        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]

    # 부분 문자열 찾기 (이 문제에서는 있는지 없는지만 찾으면 된다.)
    def find_match_idx(txt: str, pat: str) -> int:
        pt = 0
        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]
        if pp == len(pat):
            return 1
        else:
            return 0

    skip = [0] * (len(pat) + 1)
    make_skip_table(skip)
    answer = find_match_idx(txt, pat)
    print(answer)


if __name__ == '__main__':
    S = input()
    P = input()
    kmp_match(S, P)
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

링크: https://www.acmicpc.net/problem/16916

16916번: 부분 문자열