Baekjoon-16916-부분 문자열

# Boyer Moore algorithm (시간 초과 발생)

import sys
input = sys.stdin.readline

S = input().strip()
P = input().strip()

# automata
automata = {}
for i,c in enumerate(P):
    automata[c] = len(P)-1-i

i = len(P)-1
result = 0
while i < len(S):
    count = 0
    for j in range(0,-len(P),-1):
        if P[j+(len(P)-1)] == S[i+j]:
            count += 1
        else:
            i += automata.get(S[i+j], len(P)-j)+j
            break
    if count == len(P):
        result = 1
        break

print(result)

# KMP algorithm 

import sys
input = sys.stdin.readline

S = input().strip()
P = input().strip()

# pi table
def make_table(p):
    table = [0 for _ in range(len(p))]
    j = 0
    for i in range(1,len(p)):
        while j > 0 and p[j] != p[i]:
            j = table[j-1] # recursive (go to the j-1 length pi value)

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

pi_table = make_table(P)

i = 0
j = 0
for i in range(len(S)):    
    while j > 0 and S[i] != P[j]:
        j = pi_table[j-1] # j-1 !!! 주의 할 것

    if S[i] == P[j]:
        j += 1
        if j == len(P):
            print(1)
            exit()
print(0)