CLR cover
Previous problem

Problem 43: Searching Zimin Words

Next problem

The problem considers patterns that are words with variables. Besides the alphabet $\Al=\{\sa{a},\sa{b},\dots\}$ of constant letters, variables are from the (disjoint) alphabet $\mathtt{V}=\{\alpha_1,\alpha_2,\dots\}$.

A pattern $P\in\mathtt{V}^*$ is said to match a word $w\in\Al^*$ if $w=\psi(P)$, where $\psi : \alph(P)^+\rightarrow \Al^+$ is a morphism. Zimin words $Z_n$, $n\geq 0$, play a crucial role in pattern avoidability questions (see Problem 93). They are defined by $$Z_0=\varepsilon \mbox{ and } Z_n = Z_{n-1}\cdot \alpha_n\cdot Z_{n-1}.$$ For example, $Z_1=\alpha_1$, $Z_2=\alpha_1\alpha_2\alpha_1$ and $Z_3=\alpha_1\alpha_2\alpha_1\alpha_3\alpha_1\alpha_2\alpha_1$.

The Zimin type of a word $w$ is the greatest natural integer $k$ for which $w=\psi(Z_k)$, where $\psi$ is some morphism. The type is always defined since the empty word has type $0$ and the type of a non-empty word is at least $1$.

Show how to compute in linear time Zimin types of all prefixes of a given word.
Consider short borders of prefixes.

Show how to check in quadratic time if a given Zimin pattern occurs in a word.
Consider Zimin types of words.