Given a pattern $p = s_1x_1s_2x_2\cdots s_{ r-1}x_{ r-1}s_r$ such that $x_1,x_2,\ldots,x_{ r-1}\in\{ x,\overset{ { }_{ \leftarrow}}{ x}\}$, where $x$ is a variable and $\overset{ { }_{ \leftarrow}}{ x}$ its reversal, and $s_1,s_2,\ldots,s_r$ are strings that contain no variables, we describe an algorithm that constructs in $O(rn)$ time a compact representation of all $P$ instances of $p$ in an input string of length $n$ over a polynomially bounded integer alphabet, so that one can report those instances in $O(P)$ time.

Categories: cs.DS

Detecting One-variable Patterns