# 「CF-526D」Om Nom and Necklace-后缀数组

Om Nom knows that his girlfriend loves beautiful patterns. That’s why he wants the beads on the necklace to form a regular pattern. A sequence of beads S is regular if it can be represented as S = A + B + A + B + A + … + A + B + A, where A and B are some bead sequences, “ + “ is the concatenation of sequences, there are exactly 2k + 1 summands in this sum, among which there are k + 1 “A” summands and k “B” summands that follow in alternating order. Om Nelly knows that her friend is an eager mathematician, so she doesn’t mind if A or B is an empty sequence.

Help Om Nom determine in which ways he can cut off the first several beads from the found thread (at least one; probably, all) so that they form a regular pattern. When Om Nom cuts off the beads, he doesn’t change their order.

CF-526D

### 题解

$$g[sa[i]]=\left\{\begin{matrix}min(g[sa[i + 1]], height[i + 1]) & i \in (0, rank[0] - 1] \cap \{i | height[i + 1] \neq 0\} & \\ min(sa[i - 1], height[i]) & i \in [rank[0] + 1, n) \cap \{i | height[i] \neq 0\} \end{matrix}\right.$$