[백준] 16916 부분 문자열 - KMP 파이썬

문제

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

16916번: 부분 문자열

부분 문자열

시간제한	메모리 제한	제출	정답	맞힌사람	정답비율
1 초	512 MB	6354	1927	1410	36.191%

문제

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 

 

---

풀이

천천히 생각해 봤는데 내가 알고 있는 알고리즘으로는 O(N*M)보다 시간을 단축할 방법이 없었다.

찾아보니 부분 문자열을 찾아주는 KMP알고리즘이 있었다.

KMP는 O(N+M)의 시간복잡도를 가진다.

 

간단히 설명하면 KMP는 패턴이 갖는 특징을 통해 반복을 최소화하는 알고리즘이다.

이 분들이 잘 설명해 두셨다.

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

https://velog.io/@mein-figur/PythonKMP-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[Python]KMP 알고리즘

https://devbull.xyz/python-kmp-algorijeumeuro-munjayeol-cajgi/

[Python] KMP 알고리즘으로 문자열 찾기

 

import sys
word = input()
pattern = input()

# KMP 알고리즘을 수행하기 전, 패턴을 처리하는 함수
# 패턴의 테이블 생성
def KMP_table(pattern):
    lp = len(pattern)
    tb = [0 for _ in range(lp)]  # 정보 저장용 테이블

    pidx = 0  # 테이블의 값을 불러오고, 패턴의 인덱스에 접근
    for idx in range(1, lp):  # 테이블에 값 저장하기 위해 활용하는 인덱스
        # pidx가 0이 되거나, idx와 pidx의 pattern 접근 값이 같아질때까지 진행
        while pidx > 0 and pattern[idx] != pattern[pidx]:
            pidx = tb[pidx - 1]

        # 값이 일치하는 경우, pidx 1 증가시키고 그 값을 tb에 저장
        if pattern[idx] == pattern[pidx]:
            pidx += 1
            tb[idx] = pidx

    return tb

def KMP(word, pattern):
    # KMP_table 통해 전처리된 테이블 불러오기
    table = KMP_table(pattern)

    results = []  # 결과를 만족하는 인덱스 시점을 기록하는 리스트
    pidx = 0

    for idx in range(len(word)):
        # 단어와 패턴이 일치하지 않는 경우, pidx를 table을 활용해 값 변경
        while pidx > 0 and word[idx] != pattern[pidx]:
            pidx = table[pidx - 1]
        # 해당 인덱스에서 값이 일치한다면, pidx를 1 증가시킴
        # 만약 pidx가 패턴의 끝까지 도달하였다면, 시작 인덱스 값을 계산하여 추가 후 pidx 값 table의 인덱스에 접근하여 변경
        if word[idx] == pattern[pidx]:
            if pidx == len(pattern) - 1:
                results.append(idx - len(pattern) + 2)
                pidx = table[pidx]
            else:
                pidx += 1

    return results

if KMP(word, pattern):
    print(1)
else:
    print(0)

사실 완벽하게 이해하진 못한 것 같다.

다음에 나오면 다시 풀어봐야겠다.