Writing with a Stamp

Using a stamp is free, so apply it at every matching occurrence. For a stamp of length $x$, let its occurrence endpoints be $p_1<\cdots<p_k$, with adjacent gaps $d_i=p_{i+1}-p_i$. Coverage and effort are

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

Also consider the no-stamp cost $AN$.

Each suffix automaton state $v$ represents substrings with the same occurrence endpoint set and lengths

$$L=\operatorname{len}(\operatorname{link}(v))+1 \quad\text{through}\quad R=\operatorname{len}(v).$$

Find an optimal length in this interval for each state.

If $B\leq A$, choose $x=R$. Otherwise, set $r=\lfloor(B-1)/A\rfloor$. If , choose . In the remaining case, find the -th largest gap and choose

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

If $c,z$ are the count and sum of gaps smaller than the chosen length, evaluate coverage as $C(x)=x+z+(k-1-c)x$.

Obtain endpoint sets by merging upward along the suffix-link tree. Always insert the smaller set into the larger one: each endpoint moves only $O(\log N)$ times. Maintain endpoints in an ordered set. Inserting an endpoint removes the old gap between its neighbors and creates up to two new gaps. A segment tree storing gap counts and sums supports these updates, prefix statistics, and order-statistic queries in $O(\log N)$ each.

The answer is the minimum over all state optima and $AN$. The total complexity is $O(N\log^2 N)$ time and $O(N\log N)$ space.

Proof

All matching occurrences of a stamp agree wherever they overlap. The first occurrence covers $x$ positions, and every subsequent occurrence adds $\min(d_i,x)$ new positions, giving the formula for $C(x)$. Every substring belongs to one SAM state and length, so optimizing every state considers every useful stamp.