[BOJ 1786] 찾기 (Python)

복습 요망!!

풀이

이 문제의 포인트는 KMP 알고리즘을 사용하는 것이다. 문제의 설명 자체가 KMP 알고리즘의 원리이다. 결국 'KMP 알고리즘을 구현해봐!' 라는 문제의 의도를 파악할 수 있다.

KMP 알고리즘이란 주어진 문자열에서 특정한 문자열을 빠르게 찾아내는 방법 중 하나이다. KMP 알고리즘에 대해 자세히 알고싶다면 아래의 링크를 클릭하면 된다. (본인도 아직 제대로 이해하지 못해 추가적인 설명이 어렵다...)

링크 : https://devbull.xyz/python-kmp-algorijeumeuro-munjayeol-cajgi/
링크2 : https://bowbowbow.tistory.com/6

※ KMP 알고리즘 말고도 라빈 카프 알고리즘이라는 문자열 검색 알고리즘이 있다. 해시값을 이용한 빠른 문자열 검색 방법으로, 충돌이 일어난다는 단점이 있다.

※ 문자열 일치 문제는 문자열의 끝에 집중하는 스택을!
특정 조건을 만족하는 문자열 길이 문제는 표를 이용한 DP를!
찾고자 하는 문자열의 접두사와 접미사가 일치한다면 KMP를 사용하면 된다!

코드

import sys

input = sys.stdin.readline
text = input().rstrip()
pattern = input().rstrip()

answer = 0
idx = []


# Longest proper prefix which is suffix
def compute_LPS(string, lps):
    length = 0

    i = 1
    while i < len(string):
        if string[i] == string[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1


def KMP(txt, patt):
    global answer, idx
    N = len(txt)
    M = len(patt)
    lps = [0] * M

    compute_LPS(patt, lps)

    i = 0
    j = 0
    while i < N:
        if patt[j] == txt[i]:
            i += 1
            j += 1
        elif patt[j] != txt[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
        if j == M:
            idx.append(i - j + 1)
            answer += 1
            j = lps[j - 1]


KMP(text, pattern)
print(answer)
print(*idx)