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

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

16916번: 부분 문자열

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)