Editorial for Frankenstein's Banner

Frankenstein's Banner - Editorial

Author: Parsa Pordastan

Since each copy can be shortened to any prefix, let $f[p]$ be the longest template prefix matching $S$ at position $p$, and set $R[p]=p+f[p]$. One copy can then cover any interval $[p,q)$ with $p<q\leq R[p]$. Taking the longest piece is not always optimal: with templates ab and bcde, forming abcde requires a followed by bcde. Instead, we need to track the farthest endpoint reachable with a given number of copies.

To find $f[p]$, build a suffix array and LCP array for $t_1\#t_2\#\cdots t_n\#S$, where the separator is outside the lowercase alphabet. Mark the suffixes starting at template beginnings. For each suffix of $S$, its best match is one of the nearest marked suffixes on either side: suffixes sharing a prefix form a contiguous interval, so a farther marked suffix cannot match better than the nearer one. Since the LCP of two suffixes is the minimum adjacent LCP between their ranks, two sweeps maintaining these minima give all $f[p]$ in linear time after construction.

For a query starting at $l$, the endpoints reachable with at most $k$ copies form an interval $[l,F_k]$: any construction can be stopped early by shortening its last piece. Hence $F_{k+1}=\max_{l\leq p\leq F_k}R[p]$, with $R[L]=L$. This recurrence can be represented by a fixed transition: let $\operatorname{next}[p]$ maximize $R[q]$ over $p<q\leq R[p]$, keeping it only if $R[q]>R[p]$. The invariant is that every position from $l$ through the current $p$ has reach at most $R[p]$, so only positions in $(p,R[p]]$ can extend the frontier. Choosing the maximum preserves this invariant, since all positions through the chosen $q$ were either already covered or included in that maximum. Thus following $\operatorname{next}$ gives the optimal frontiers for successive copy counts. A segment tree computes these transitions in $O(L\log L)$ time.

Binary lifting over $\operatorname{next}$ answers each query in $O(\log L)$: starting at $l$, skip transitions while the resulting reach remains below $r$, then take the final transition that reaches it. The initial state counts as one copy, and each transition adds one; if the chain ends before reaching $r$, the answer is $-1$. Reaching beyond $r$ suffices because the last piece can be shortened. With $L=|S|$ and $N=L+\sum_i|t_i|+n$, an $O(N\log N)$ suffix-array construction gives total time $O(N\log N+(L+m)\log L)$ and memory $O(N+L\log L)$.