BOJ - 1786 - 찾기

def getPartialMatch(P):
    pLength = len(P)

    pi = [0 for _ in range(pLength)]
    start = 1
    match = 0

    while start + match < pLength:
        if P[start + match] == P[match]:
            match += 1
            pi[start + match - 1] = match
        else:
            if match == 0:
                start += 1
            else:
                start += match - pi[match - 1]
                match = pi[match - 1]
    return pi

def KMP(T, P):
    tLength = len(T)
    pLength = len(P)
    ret = []

    pi = getPartialMatch(P)
    start = 0
    match = 0

    while start <= tLength - pLength:
        if match < pLength and T[start + match] == P[match]:
            match += 1
            if match == pLength:
                ret.append(start)
        else:
            if match == 0:
                start += 1
            else:
                start += match - pi[match - 1]
                match = pi[match - 1]
    return ret

def solution():
    T = str(input())
    P = str(input())

    result = KMP(T, P)
    print(len(result))
    for r in result:
        print(r + 1, end=' ')

solution()

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