[백준 16916] 부분 문자열

문제

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

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

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

 

입력

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

 

출력

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

---

접근

kmp 알고리즘을 적용하여 부분 문자열을 찾았다.

인덱스 i는 S, 인덱스 j는 P를 가리킨다고 했을 때 S의 길이만큼 i가 순차적으로 증가한다. j는 0부터 시작하여 S[i] == P[j]일 때 1씩 증가시킨다. 이 과정에서 S[i] != P[j]일 때는 최대 접미사, 접두사를 찾은 테이블을 활용하여 인덱스 j를 같은 문자가 나올 때까지 갱신시킨다. 

즉 i는 그대로 진행되고 j만 계속해서 업데이트되면서 부분 문자열을 찾게된다.

 

구현

- 찾아야하는 부분 문자열 P에 대해 최대 접미사, 접두사를 table에 기록한다.

def make_table(p):
    global table

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

        if p[i] == p[j]:
            j += 1
            table[i] = j

- 이제 S에서 부분 문자열 P를 찾는다.

- S를 순차적으로 탐색하여 j가 가리키는 P의 무낮와 같을 때 j를 증가시킨다.

- 다를 경우 테이블을 활용하여 j 인덱스를 갱신시킨다. 이를 통해 처음부터 탐색하는 것을 방지하여 시간복잡도를 줄일 수 있다.

- 이제 인덱스 j가 P의 길이 - 1이라면 S 내에 P가 존재하는 것이기 때문에 True를 반환한다.

def solve(s, p):
    global 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
            j += 1
    return False

---

전체 코드

def make_table(p):
    global table

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

        if p[i] == p[j]:
            j += 1
            table[i] = j

def solve(s, p):
    global 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
            j += 1
    return False

S = list(input())
P = list(input())

table = [0] * len(P)

make_table(P)
answer = solve(S, P)
if answer:
    print(1)
else:
    print(0)