[백준/Python3] 12780번 원피스

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

12780번: 원피스

문제

바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 놓고 왔다는 것이었다. 원피스를 가진 자는 이 세상을 가질 수 있다는 매혹적인 얘기였다.

모두들 말도 안 된다고 고개를 저었지만 교정이는 동료를 모아 원피스를 찾아 여행을 떠났다. 하늘섬을 지나 어인섬도 지나고 사황을 무너뜨린 뒤 교정이와 동료들은 결국 원피스의 위치가 적힌 결정적인 단서를 찾아냈다. 이 단서는 한 눈에 봐서는 해독이 어려웠다. 왜냐하면 여기에는 그저 알파벳 대문자들이 연속해서 적혀있었기 때문이다.

하지만 천재적인 두뇌를 가진 교정이의 동료이자 해적단의 항해사 진아는 단번에 이 단서에 어떤 특정 문자열이 여러 번 등장한다는 것을 직감했다.

이 특정 문자열이 어떤 문자열인지는 잘 알 수 없었던 진아는 자신이 생각한 모든 문자열이 이 단서에서 총 몇 번 등장하는지 알아보기로 했다. 아마도 가장 많이 등장한 문자열이 원피스의 위치를 알려줄 것이라고 생각했기 때문이다.

진아는 밀짚모자 해적단의 프로그래밍 담당인 당신에게 도움을 요청했다. 단서 전체에 진아가 원하는 문자열이 몇 번 등장하는지 알아내는 프로그램을 작성하라.

입력

입력의 첫 줄에는 해적단이 획득한 단서의 문자열 H가 주어진다.(0 < |H| ≤ 100,000)

입력의 두 번째 줄에는 진아가 H에서 등장 횟수를 알고 싶은 문자열 N이 주어진다.(0 < |N| ≤ 10)

단, N과 H는 공백 없는 문자열로 주어지며, 모두 알파벳 대문자로 이루어져 있다.

출력

H에서 N이 몇 번 등장하는지 출력한다.

 

<풀이과정>

이 문제를 처음 접했을 때, 물론 다른 쉬운 풀이도 있겠다 싶었지만 

지난 학기 알고리즘 해석 및 설계 시간에 배웠던 KMP 알고리즘을 통해 문제를 해결해보고자 했다.

def KMP(string, pattern)

은 해적단이 획득한 단서(string)과 등장 횟수를 알고싶은 문자열(pattern)을 입력으로 받는다. 

등장 횟수를 알기위한 변수 res와 실패함수 테이블의 저장을 위한 failure라는 변수를 정의했다.

failure = failureFuntion(len(pattern), pattern)

(*실패함수: 더 효율적인 탐색을 위해 어느 위치에서 mismatch 발생 시, 몇 칸 이후를 검사할지에 대한 정보를 미리 넣어놓은 table을 구함.)

failure에 해당 정보가 넘어오면, 

KMP로 넘어온 string(획득한 단서)를 한 글자씩 순회하면서 pattern에 해당하는 문자열이 나왔는지 확인하고, 해당 문자열이 나왔을 시, res(문제의 결과값)에 +1 씩 하여 return 시키면, 문제를 풀 수 있다.

 

KMP 함수의 진행 과정은 이렇다. 

* i: 현재 string 문자열의 id

* j: 현재까지 매칭된 pattern의 길이

for loop을 통해 string을 한 글자씩 순회하면서.

while loop으로 들어가 j가 0보다 크고, string의 i번째 글자와 pattern의 j번째 글자가 다를 시                       

pattern의 j - 1번째 문자까지는 맞았다는 이야기 이므로, j = failure[j - 1]로 업데이트 한다.             

string[i]와 pattern[j]가 같은 경우,                       

j == len(patten) - 1 이라면 패턴을 찾은 것이므로 res에 +1 시키고 j를 이전까지 매칭된 부분의 길이로 업데이트 한다.                       

그렇지 않은 경우, (지금까지는 다 맞았는데 아직 뒤에가 좀 남은 경우)에는 j값을 +1 시켜 검사가 계속 되도록 한다.

 

이 과정을 string의 모든 문자에 대해 반복하면 답을 얻을 수 있다. 

<정답 코드>

def failureFuntion(length, str):

    #초기 f(0)의 값은 0임이 자명함
    f_of_i = [0]

    for i in range(1, length):
        j = f_of_i[i - 1]
        # f_of_i[i - 1]이 0보다 크고, 패턴의 i번째 글자와 j번째 글자가 같지 않다면, 이전까지 가장 긴 접두사 접미사에 대한 검사를 함
        while j > 0 and str[i] != str[j]:
            j = f_of_i[j - 1]

        # 패턴의 i번째 글자와 j번째 글자가 같다면, 실패함수 값에 1을 더함
        if str[i] == str[j]:
            j += 1

        # j값을 테이블에 추가
        f_of_i.append(j)
    return f_of_i

def KMP(string, pattern):
    res = 0
    failure = failureFuntion(len(pattern), pattern)
    j = 0
    for i in range(len(string)):
        while j > 0 and string[i] != pattern[j]:
            j = failure[j - 1]
        if string[i] == pattern[j]:
            if j == len(pattern) - 1:
                res += 1
                j = failure[j]
            else:
                j += 1
    return res

H = input()
N = input()

print(KMP(H, N))