백준 1786 - 찾기 (Python)

KMP 알고리즘을 사용하면 됩니다.

전체 코드

import sys

input = sys.stdin.readline

T = input().replace('\n', '')
P = input().replace('\n', '')

T_SIZE = len(T)
P_SIZE = len(P)

table = [0] * P_SIZE

def make_table():
    j = 0
    for i in range(1, P_SIZE):
        while j > 0 and P[i] != P[j]:
            j = table[j - 1]
        if P[i] == P[j]:
            j += 1
            table[i] = j

def KMP():
    make_table()
    j = 0
    result = []
    
    for i in range(T_SIZE):
        while j > 0 and T[i] != P[j]:
            j = table[j - 1]
        if T[i] == P[j]:
            if j == P_SIZE - 1:
                result.append(i - P_SIZE + 2)
                j = table[j]
            else:
                j += 1

    return result

answer = KMP()

print(len(answer))
print(*answer)