백준 16916번: 부분 문자열 python 풀이 및 정답 코드

문제 링크

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

16916번: 부분 문자열

 

 

문제 설명

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.

예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.

문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.

 

 

문제 풀이

처음엔 단순히 문자열 검사로 풀려고 했으나... 시간 초과가 떴다 당연함 골드임

그래서 찾아봤더니 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

s = input()
p = input()
print(1 if kmp() else 0)

 

 

결과

 

 

 

다른 사람의 코드

 

 

 

리뷰