[Python] BOJ 16916 - 부분 문자열

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

16916번: 부분 문자열

# KMP알고리즘을 사용하여 풀었다.

# 아직 정확히 이해하진 못해서, 나중에 이해한 뒤 다시 정리할 예정이다.

 

def KMP():
    table = make_table()
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = table[j - 1]

        if s[i] == p[j]:
            if j == len(p)-1:
                return True
            else:
                j += 1
    return False

def make_table():
    table = [0] * len(p)
    j = 0
    for i in range(1, len(p)):
        while j > 0 and p[i] != p[j]:
            j = table[j - 1]

        if p[i] == p[j]:
            j += 1
            table[i] = j
    return table

s = input()
p = input()
if KMP():
    print(1)
else:
    print(0)

(solved.ac 티어: 골드 4)