Detecting one-variable patterns

Abstract

Given a pattern p = s1x1s2x2 … sr-1xr-1sr such that (Formula presented), where x is a variable and x its reversal, and s1,s2, …, sr 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. © Springer International Publishing AG 2017.