CEO

문제 16916번: 부분 문자열 첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문제 풀이 문자열 S, P가 주어질 때 P가 S의 부분 문자열인지 판단하여 결과를 반환하는 문제이다. 두 문자열의 길이는 100만 미만이므로 단순히 `print(int(p in s))`와 같이 풀게 되면 시간 초과가 발생한다. 따라서 `KMP 알고리즘`을 활용하여 필요 없는 곳의 탐색을 건너뛰도록 하여야 시간 내에 통과할 수 있다. 문제를 풀기 위해서는 `KMP 알고리즘`을 이해하고 구현하면 쉽게 해결할 수 있다. 코드 def make_table(): length = len(p) ta..