Detecting Unary Patterns.
Dmitry Kosolobov, Florín Manea, Dirk Nowotka · arXiv (Cornell University) · 2016
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$, so that one can report those occurrences in $O(P)$ time.