KMP 문자열 매칭

문제 설명

Knuth-Morris-Pratt(KMP) 알고리즘을 구현하여 텍스트에서 패턴이 등장하는 모든 위치를 찾으세요.

KMP 알고리즘

실패 함수(failure function)를 이용해 불필요한 비교를 줄이는 문자열 매칭 알고리즘입니다.

입력 형식

첫 줄: 텍스트 T

둘째 줄: 패턴 P

출력 형식

패턴이 등장하는 모든 시작 인덱스 (0-indexed, 공백 구분)

제약 조건

• 1 ≤ |P| ≤ |T| ≤ 1,000,000

예시

T = "ABABDABACDABABCABAB"
P = "ABABCABAB"
출력: 10

T = "AABAACAADAABAABA"
P = "AABA"
출력: 0 9 12