[KMP] 백준 16916번 : 부분 문자열 / 골드 3

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

16916번: 부분 문자열

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

www.acmicpc.net

KMP를 몰랐다면 시간때문에 좀 힘들었을 것 같으나,

난 KMP를 공부했기 때문에 쉽다.

def kmp(all_string, pattern):
    #  kmp_table
    table = [0 for _ in range(len(pattern))]
    i = 0
    for j in range(1, len(pattern)):
        while i > 0 and pattern[i] != pattern[j]:
            i = table[i-1]

        if pattern[i] == pattern[j]:
            i += 1
            table[j] = i

    #  kmp
    i = 0
    for j in range(len(all_string)):
        while i > 0 and pattern[i] != all_string[j]:
            i = table[i-1]

        if pattern[i] == all_string[j]:
            i += 1
            if i == len(pattern):
                print(1)
                quit()

    print(0)

a = input()
b = input()
kmp(a, b)