[백준][문자열] 부분 문자열

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

16916번: 부분 문자열

 

내가 작성한 코드

import sys
read = sys.stdin.readline

s = read().rstrip()
p = read().rstrip()

def make_table(s: str) -> list[int]:
    table = [0] * len(s)
    j = 0
    for i in range(1, len(s)):
        c = s[i]
        while j > 0 and s[j] != c:
            j = table[j-1]
        if s[j] == c:
            j += 1
            table[i] = j
    return table

table = make_table(p)
i = ans = 0
for c in s:
    while i > 0 and p[i] != c:
        i = table[i - 1]

    if p[i] == c:
        i += 1

    if i == len(p):
        ans = 1
        break

print(ans)

• KMP로 패턴의 중복까지 확인하여 탐색
  
  • ababc 패턴을 abababc에서 찾을 때, 탐색 실패시 패턴의 처음부터 찾으면 탐색을 실패함

 

다른 사람이 작성한 코드

def getPI(pattern):
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j

def KMP(s, pattern):
    getPI(pattern)
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != pattern[j]:
            j = pi[j - 1]
        if s[i] == pattern[j]:
            if j == len(pattern) - 1:
                return True
            else:
                j += 1
    return False

s = input()
pattern = input()
pi = [0 for x in range(len(pattern))]

if KMP(s, pattern):
    print('1')
else:
    print('0')

• 비슷하게 구현했다

https://www.landlordgang.xyz/82

[백준 16916 파이썬] 부분 문자열(KMP 알고리즘)

기억해야할 것

• KMP 알고리즘 활용
  • 여러 문자열 문제를 풀었는데, 많이 사용되는 것 같다
  • 특정 문자열의 포함을 확인할 때는 필수
    - 단순 brute-force로는 패턴 내의 중복이 고려되지 않음
• KMP 알고리즘 이해
  • 문자열의 포함 관계를 확인할 때 사용
  • 등장 인물
    - 문자열
    - 패턴
    - table
  • 문자열
    - 탐색의 대상이 되는 문자열, 문자의 일치 여부로만 확인
  • 패턴
    - (주인공) table을 작성할 때도 사용하고, 인덱스가 종료를 확인하거나 알고리즘에 중요한 역할
  • table
    - 패턴의 탐색에서 중복 확인에 사용