Writing with a Stamp

도장을 찍는 것은 무료이므로, 도장 문자열을 정했다면 등장하는 모든 위치에 찍는다. 길이 $x$인 도장의 등장 끝 위치를 $p_1<\cdots<p_k$, 인접 간격을 $d_i=p_{i+1}-p_i$라 하자. 덮이는 위치 수와 필요한 힘은 각각

$$C(x)=x+\sum_{i=1}^{k-1}\min(d_i,x),\qquad F(x)=Bx+A(N-C(x))$$

이다. 도장을 만들지 않는 비용 $AN$도 비교한다.

접미사 자동자(SAM)의 각 상태 $v$는 등장 끝 위치 집합이 같은 부분 문자열들을 나타낸다. 그 길이 범위는

$$L=\operatorname{len}(\operatorname{link}(v))+1,\qquad R=\operatorname{len}(v)$$

이다. 상태마다 이 범위에서 최적 길이 하나를 구한다.

$B\leq A$이면 $x=R$을 고른다. 그렇지 않으면 $r=\lfloor(B-1)/A\rfloor$로 둔다. 이면 을 고르고, 나머지는 번째로 큰 간격 를 구해

$$x=\min(R,\max(L,d))$$

로 정한다. 선택한 $x$보다 작은 간격의 개수와 합을 $c,z$라 하면 $C(x)=x+z+(k-1-c)x$로 계산한다.

끝 위치 집합은 suffix link 트리의 아래쪽에서 위쪽으로 합친다. 작은 집합의 위치들을 큰 집합에 삽입하면 각 위치는 $O(\log N)$번만 이동한다. 위치들을 정렬된 집합으로 관리하면 삽입 시 이웃 사이의 간격 하나를 지우고 새 간격을 최대 두 개 추가하면 된다. 간격의 개수와 합을 저장하는 세그먼트 트리로 갱신, 부분합, 순위 질의를 각각 $O(\log N)$에 처리한다.

모든 상태의 최소 비용과 $AN$ 중 최솟값이 정답이다. 시간 복잡도는 $O(N\log^2 N)$, 공간 복잡도는 $O(N\log N)$이다.

증명

같은 도장은 모든 등장 위치에 찍어도 서로 모순되지 않는다. 첫 도장은 $x$개 위치를 덮고, 이후 도장은 직전 끝 위치와의 간격에 따라 $\min(d_i,x)$개씩 새로 덮으므로 $C(x)$의 식을 얻는다. 모든 부분 문자열은 SAM의 어느 상태와 길이에 대응하므로, 각 상태에서 최적 길이를 구하면 모든 유용한 도장을 고려한다.

끝 위치 집합이 고정되어 있을 때