Z 알고리즘

길이가 $N$인 문자열 $S$가 주어진다. 배열 $a_0, a_1, ..., a_{N - 1}$을 다음과 같이 계산한다.

• $a_i$는 $S$과 $S.substr(i)$의 LCP(최장 공통 접두사)이다.

제약 조건

• $1 \leq N \leq 500000$
• $S$의 각 문자는 영문 소문자이다.

$S$

$a_0$ $a_1$ $a_2$ ... $a_{N-1}$