  Suffix trees are an important data structure at the core of optimal solutions
to many fundamental string problems, such as exact pattern matching, longest
common substring, matching statistics, and longest repeated substring. Recent
lines of research focused on extending some of these problems to vertex-labeled
graphs, although using ad-hoc approaches which in some cases do not generalize
to all input graphs. In the absence of a ubiquitous tool like the suffix tree
for labeled graphs, we introduce the labeled direct product of two graphs as a
general tool for obtaining optimal algorithms: we obtain conceptually simpler
algorithms for the quadratic problems of string matching (SMLG) and longest
common substring (LCSP) in labeled graphs. Our algorithms are also more
efficient, since they run in time linear in the size of the labeled product
graph, which may be smaller than quadratic for some inputs, and their run-time
is predictable, because the size of the labeled direct product graph can be
precomputed efficiently. We also solve LCSP on graphs containing cycles, which
was left as an open problem by Shimohira et al. in 2011. To show the power of
the labeled product graph, we also apply it to solve the matching statistics
(MSP) and the longest repeated string (LRSP) problems in labeled graphs.
Moreover, we show that our (worst-case quadratic) algorithms are also optimal,
conditioned on the Orthogonal Vectors Hypothesis. Finally, we complete the
complexity picture around LRSP by studying it on undirected graphs.

Data Structures and Algorithms;Computational Complexity