bj1786 찾기

문제

• 백준 URL: 찾기
• 난이도 플래티넘 5

풀이

import sys

T = input()
P = input()

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

def kmp(text, pattern):
    pi = get_pi(pattern)
    n,m = len(text),len(pattern)
    matched = []
    j = 0
    for i in range(n):
        while j > 0 and text[i] != pattern[j]:
            j = pi[j-1]
        if text[i] == pattern[j]:
            if j == m-1:
                matched.append(i-m+2)
                j = pi[j]
            else: j+=1
    return matched

result = kmp(T,P)

print(len(result))
print(*result)

KMP 알고리즘은 '실패 함수' 또는 'Pi 배열'이라고 불리는 전처리 배열을 사용한다. pi[i]의 값은 패턴의 0번 인덱스부터 i번 인덱스까지의 부분 문자열에서, 접두사(prefix)와 접미사(suffix)가 일치하는 가장 긴 길이를 의미한다.

def get_pi(pattern):
    m = len(pattern)
    pi = [0] * m
    j = 0  # 일치하는 접두사의 길이
    for i in range(1, m):
        # 현재 j 위치의 문자와 i 위치의 문자가 다르면, j를 이전 pi 값으로 되돌림
        while j > 0 and pattern[i] != pattern[j]:
            j = pi[j - 1]
        # 문자가 일치하면 j를 1 증가시키고 pi[i]에 저장
        if pattern[i] == pattern[j]:
            j += 1
            pi[i] = j
    return pi

• 이 함수는 패턴 문자열 pattern을 입력받아 Pi 배열을 계산하여 반환한다.
• j는 현재까지 일치한 접두사와 접미사의 길이를 나타낸다
• i를 1부터 m-1까지 순회하면서 pi 배열을 채운다.
• pattern[i]와 pattern[j]가 일치하지 않으면, j를 pi[j-1] 값으로 갱신하며 일치하는 부분을 찾을 때까지 거슬러 올라간다. 이는 다음으로 비교할 위치를 찾는 과정이다.
• pattern[i]와 pattern[j]가 일치하면, j를 1 증가시켜 pi[i]에 저장한다.

def kmp(text, pattern):
    pi = get_pi(pattern)
    n = len(text)
    m = len(pattern)
    matched_positions = []
    j = 0  # 패턴에서 일치한 문자의 수
    for i in range(n):
        # 텍스트와 패턴 문자가 다르면, pi 배열을 이용해 j 위치 조정
        while j > 0 and text[i] != pattern[j]:
            j = pi[j - 1]
        # 문자가 일치하는 경우
        if text[i] == pattern[j]:
            # 패턴의 끝까지 모두 일치했다면
            if j == m - 1:
                matched_positions.append(i - m + 2) # 1-based 인덱스로 저장
                j = pi[j] # 다음 매칭을 위해 j 위치 조정
            else:
                j += 1
    return matched_positions

• 이 함수는 get_pi를 통해 얻은 pi 배열을 이용하여 실제 문자열 매칭을 수행한다.
• i는 텍스트를 순회하는 인덱스, j는 패턴을 순회하는 인덱스이다.
• text[i]와 pattern[j]가 일치하지 않으면, get_pi에서와 동일한 원리로 j = pi[j-1]을 통해 j의 위치를 효율적으로 이동시킨다.
• 문자가 일치하고 패턴의 끝(j == m-1)까지 도달했다면, 매칭에 성공한 것이다.
  • 매칭 시작 위치(i - m + 2)를 matched_positions 리스트에 추가한다.
  • j = pi[j]를 통해 다음 매칭 가능성이 있는 위치로 j를 이동시킨다.
• 문자가 일치했지만 패턴의 끝이 아니라면, j를 1 증가시켜 다음 문자를 비교한다.