[알고리즘][Python] 백준 1786 찾기 문제 풀이

문제 출처 : www.acmicpc.net/problem/1786

1786번: 찾기

---

문제 해석 : 문자열을 탐색하는 것을 KMP 알고리즘으로 구현할 수 있는가를 묻는 문제이다.

 

문제 풀이 : 유명한 알고리즘인 KMP 알고리즘을 활용하여 풀이할 수 있다.

 

- 다음 링크에 상세하게 알고리즘 동작 과정에 대해서 설명해 놓았다.

LINK : bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

---

풀이 코드

def make_pi():
    pi = [0 for i in range(0, len(P))]

    j = 0
    for i in range(1, len(P)):
        while j > 0 and P[i] != P[j]:
            j = pi[j - 1]

        if (P[i] == P[j]):
            j += 1
            pi[i] = j
    return pi


def solution(pi):
    result = []
    count = 0

    j = 0
    for i in range(0, len(T)):

        while j > 0 and T[i] != P[j]:
            j = pi[j - 1]

        if T[i] == P[j]:
            if j == (len(P) - 1):
                result.append(i - len(P) + 2)
                count += 1
                j = pi[j]
            else:
                j += 1

    print(count)
    for element in result:
        print(element)


T = input()
P = input()
solution(make_pi())

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.