[백준] 16916번 > 부분 문자열

www.acmicpc.net/problem/16916

16916번: 부분 문자열

문제

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

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

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

입력

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

예제 입력 1

baekjoon

aek

예제 출력 1

1

예제 입력 2

baekjoon

bak

예제 출력 2

0

예제 입력 3

baekjoon

joo

예제 출력 3

1

예제 입력 4

baekjoon

oone

예제 출력 4

0

예제 입력 5

baekjoon

online

예제 출력 5

0

예제 입력 6

baekjoon

baekjoon

예제 출력 6

1

 

---

풀이

첫번째 풀이 : 단순히 if p in s를 사용하였음 ==> 시간 초과

import sys
s = sys.stdin.readline().strip()
p = sys.stdin.readline().strip()
if p in s:
    print(1)
else:
    print(0)

두번째 풀이 : 슬라이싱을 사용하여 문자열 비교 ==> 시간 초과

import sys
s = sys.stdin.readline().strip()
p = sys.stdin.readline().strip()
for i in range(len(s)-len(p) + 1):
    if s[i:i+len(p)] == p:
        print(1)
        break
else:
    print(0)

 

세번째 풀이 : KMP 알고리즘 사용

import sys
s = sys.stdin.readline().strip()
p = sys.stdin.readline().strip()
def getPartialMatch(N):
    m = len(N)
    pi = [0] * m
    # KMP로 N에서 N을 찾는다 (begin은 1부터)
    begin = 1
    matched = 0
    # 비교할 문자가 N의 끝에 도달할 때까지 부분 일치를 모두 기록
    while begin + matched < m:
        if N[begin + matched] == N[matched]:
            matched += 1
            pi[begin + matched - 1] = matched
        else:
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]
    return pi

def kmpSearch(H, N):
    n = len(H)
    m = len(N)
    # 결과값 리스트
    ret = []
    # pi[i]는 N[~i]의 접두사도 되고 접미사는 되는 문자열의 최대 길이
    pi = getPartialMatch(N)
    begin = 0
    matched = 0
    while begin <= n - m:
    # 글자가 일치한다면
        if matched < m and H[begin + matched] == N[matched]:
            matched += 1
        # m글자가 모두 일치한다면
            if matched == m:
                ret.append(begin)
        else:
        # matched가 0인 경우 다음 칸에서 시작
            if matched == 0:
                begin += 1
            else:
                begin += matched - pi[matched - 1]
                matched = pi[matched - 1]
    return ret
if kmpSearch(s, p):
    print(1)
else:
    print(0)

kmp알고리즘은 따로 공부를 좀 더 해야할 필요가 있을 것 같다.