January 24, 2023

16916번: 부분 문자열

문제 요약

• 문자열 S와 P가 주어졌을 때, P가 S의 부문 문자열이라면 1을 출력하고, 그렇지 않다면 0을 출력
• 1 ≤ 문자열 길이 ≤ 1,000,000

문제풀이

def make_table(pattern):
    pattern_size = len(pattern)
    table = [0] * pattern_size

    j = 0

    for i in range(1, pattern_size):
        while (j > 0 and pattern[i] != pattern[j]):
            j = table[j - 1]

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

    return table

def kmp(parent, pattern):
    table = make_table(pattern)
    parent_size = len(parent)
    pattern_size = len(pattern)
    j = 0
    for i in range(parent_size):
        while (j > 0 and parent[i] != pattern[j]):
            j = table[j - 1]

        if (parent[i] == pattern[j]):
            if (j == pattern_size - 1):
                return 1
            else:
                j = j + 1
    return 0

parent = input()
pattern = input()
print(kmp(parent, pattern))

• KMP 알고리즘 이용