백준 1768 - 찾기

백준 1768 - 찾기

KMP 알고리즘은 문자열 검색시 불필요한 문자간의 비교를 없애기 위하여 실패함수를 이용하여 O(n+m)으로 만들어줍니다.
실패함수는 KMP알고리즘 실행중 일치하지 않는 문자가 있으면 어디서부터 검색을 할지 알려줍니다.
즉 처음부분부터 해당위치까지 접두사, 접미사가 몇개나 일치하는지 기록하는 테이블을 만듭니다.

1768 소스코드

import sys

def Make(p, 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 KMP(t, p, table):
    Make(p, table)
    j, count, size = 0, 0, len(p)
    result = []

    for i in range(len(t)):
        while j > 0 and t[i] != p[j]:
            j = table[j-1]
        if t[i] == p[j]:
            if j == size-1:
                count += 1
                result.append(i-size+2)
                j = table[j]
            else:
                j += 1
    return [count, result]
input = sys.stdin.readline

t = input().replace("\n", "")
p = input().replace("\n", "")
table = [0 for i in range(len(p))]
result = KMP(t, p, table)

print(result[0])
print(*result[1])