백준: 16916 부분 문자열

문제

16916번: 부분 문자열

 

문제 풀이

 문자열 S, P가 주어질 때 P가 S의 부분 문자열인지 판단하여 결과를 반환하는 문제이다. 두 문자열의 길이는 100만 미만이므로 단순히 `print(int(p in s))`와 같이 풀게 되면 시간 초과가 발생한다. 따라서 `KMP 알고리즘`을 활용하여 필요 없는 곳의 탐색을 건너뛰도록 하여야 시간 내에 통과할 수 있다. 문제를 풀기 위해서는 `KMP 알고리즘`을 이해하고 구현하면 쉽게 해결할 수 있다.

 

코드

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


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


if __name__ == "__main__":
    s = input()
    p = input()
    print(1 if kmp() else 0)