#340 kmp | DOJ

Loading problem...

Preparing the statement, recent submissions, and submit form.

Library Checker/String

Time limit: 3000 ms
Python time limit: 4000 ms
Memory limit: 1024 MB
Checker: TOKEN
Solve threshold: 100

Statement

알파벳 소문자로 이루어진 패턴 문자열 $P$ 와 텍스트 문자열 $S$ 가 주어진다. $P$ 가 $S$ 안에 등장하는 모든 시작 위치를 오름차순으로 출력하여라. 등장은 서로 겹칠 수 있으며, 위치는 $1$ 부터 시작한다.

Input

입력은 다음과 같은 형식으로 주어진다.

$P$ $S$

Output

첫째 줄에 등장 횟수 $K$ 를 출력한다. 둘째 줄에 $K$ 개의 시작 위치를 오름차순으로 출력한다. $K=0$ 이면 둘째 줄은 빈 줄로 출력한다.

Constraints

$1 \leq |P| \leq 500\ 000$ .
$1 \leq |S| \leq 500\ 000$ .
$|P|+|S| \leq 700\ 000$ .
두 문자열은 알파벳 소문자로만 이루어진다.

Subtasks

#	Score	Constraints
1	20	$\|P\|+\|S\| \leq 1\ 000$ 이다.
2	80	추가적인 제약조건이 없다.