[백준] 1786번 찾기 (by Python)

문제

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

1786번: 찾기

 

풀이

    parent string에 pattern string이 포함되어 있는지 찾을 수 있는 KMP 알고리즘에 대한 문제이다. KMP 알고리즘은 다음과 같다.

 

    먼저, pattern과 같은 길이의 table array를 만들어준다. 이 때 pattern에서 prefix와 같은 내용의 postfix가 있다고 가정할 때, table의 원소는 같은 index를 가진 character가 postfix에서 몇 번째 원소인지를 나타낸다. 말이 어려운 것 같아서 몇 가지 예시를 들도록 하겠다.

 

예시 1) pattern: 'abcab' => table [0, 0, 0, 1, 2]

예시 2) pattern: 'aaaaa' => table [0, 1, 2, 3, 4]

예시 3) pattern: 'abacaaba' => table [0, 0, 1, 0, 1, 1, 2, 3]

 

    그리고 나서 parent의 character을 가리키는 인덱스 i와 pattern의 character를 가리키는 인덱스 j를 둔다. 둘 다 0에서 시작하여 각각을 비교한다. 일치하지 않을 경우, 일치할 때까지 j에 table[j - 1]을 할당한다. 이는 해당 character를 비교할 수 있는 0 이상 j 미만의 최대 index를 찾게 해준다. 일치하는 것이 없을 경우, j는 0이 된다. 만약 pattern을 모두 비교해서 일치할 경우 count를 1 증가시키고 j에 table[j]를 할당하여 다시 탐색을 시작한다.

def kmp(parent, pattern):
    n = len(parent)
    m = len(pattern)
    table = [0] * m
    j = 0
    for i in range(1, m):
        while j > 0 and pattern[i] != pattern[j]:
            j = table[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
            table[i] = j
    j = 0
    count = 0
    loc = []
    for i in range(n):
        while j > 0 and parent[i] != pattern[j]:
            j = table[j - 1]
        if parent[i] == pattern[j]:
            if j == (m - 1):
                count += 1
                loc.append(i - m + 2)
                j = table[j]
            else:
                j += 1
    print(count)
    print(*loc)

t = input()
p = input()
kmp(t, p)