In [G.Kucherov and M.Rusinowitch, Undecidability of ground reducibility for word rewriting systems with variables, Information Processing Letters, 53:209--215, 1995] we proved that for a word rewriting system with variables $\R$ and a word with variables $w$, it is undecidable if $w$ is ground reducible by $\R$, that is if all the instances of $w$ obtained by substituting its variables by non-empty words are reducible by $\R$. On the other hand, if $\R$ is linear, the question is decidable for arbitrary (linear or non-linear) $w$. In this paper we futher study the complexity of the above problem and prove that it is {\it co-NP}-complete if both $\R$ and $w$ are restricted to be linear. The proof is based on the construction of a deterministic finite automaton for the language of words reducible by $\R$. The construction generalizes the well-known Aho-Corasick automaton for string matching against a set of keywords.