Detecting One-variable Patterns

Abstract

Given a pattern $p=s_1{x}_1{s}_2{x}_2\cdots s_{r-1}{x}_{r-1}{s}_r$ such that $x_1,x_2,\dots ,x_{r-1}\in \{x,\overleftarrow{x}\}$, where $x$ is a variable and $\overleftarrow{x}$ its reversal, and $s_1,s_2,\dots ,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.

16 pages (+13 pages of Appendix), 4 figures, accepted to SPIRE 2017

References in corpus (1)

• The "Runs" Theorem