[백준] 16916번 - 부분 문자열 (파이썬)

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

 

# 부분 문자열
P, S = input().strip(), input().strip()


def get_table(x):
    arr = [0 for _ in range(len(x))]
    j = 0
    for i in range(1, len(x)):
        while j > 0 and x[i] != x[j]:
            j = arr[j-1]
        if x[i] == x[j]:
            j += 1
            arr[i] = j
    return arr


def kmp(word, find):
    result = 0
    j = 0
    for i in range(len(word)):
        while j > 0 and word[i] != find[j]:
            j = table[j-1]
        if word[i] == find[j]:
            if j == len(find)-1:
                result += 1
                j = table[j]
            else:
                j += 1
    return result


table = get_table(S)
result = kmp(P, S)
print(1 if result else 0)

 

문자열, KMP
1. get_table : 접두사와 접미사가 일치하는 최대 길이를 기억
    - 같은 단어가 아니라면 j를 이전 테이블의 값으로 이동 반복
    - 같은 단어라면 j 증가, 테이블 값 j로 초기화 (j는 일치하는 단어의 길이)
2. kmp : table을 이용해서 점프를 해가며 탐색
    - 같은 단어가 아니라면 j를 이전 테이블의 값으로 이동 반복
    - 같은 단어이고 찾는 문자열이 끝났다면, result 증가, table이 가리키는 인덱스로 이동
    - 같은 단어이고 찾는 문자열이 끝이 아니라면, j 증가
3. result가 존재하면 1 아니면 0 출력

 

문자열 탐색 알고리즘인 KMP이다.

접두사와 접미사가 같은지 다른지를 확인해서 table에 기록을 해두고

그 테이블의 값을 이용하여 점프를 하며 문자열을 탐색하는 방법

abacaba
a : 0
ab : 0
aba : 1
abac : 0
abaca : 1
abacab : 2
abacaba : 3
table = [0, 0, 1, 0, 1, 2, 3]

접두사와 접미사가 같으면 해당 단어는 같다는 것을 알 수 있으니 점프해서 그다음 단어부터 탐색하는 방법이다.