How to determine if a labelled digraph contains a cycle with given labels?
The following suggestion may speed up your solution if you need to answer queries for many different words.

Define the set $U_i^w$ to be a set of pairs $(v, A)$ where $A \subseteq V$ and $v$ is reached by some vertex in $A$ after traversing the first $i$ labels of the word $w$.  Then to check if $w$ forms a cycle in the graph, loop through all $(v, A) \in U_{|w|}^w$ and if ever $v \in A$, then a cycle does exist.

Note that if the first $i$ elements of $w$ and $w&#39;$ are the same, then $U_i^w = U_i^{w&#39;}$.  Also, $U_0^w = \{(v, \{v \} ) | v \in V \} $.

As you process queries, dynamically construct a trie such that each node (including the inner nodes) stores $U_i^w$ for some $i$ and $w$.  This way, if $w$ and $w&#39;$ have the same first $k$ elements and $w$ is processed before $w&#39;$, then $U_k^{w&#39;}$ can be quickly retrieved by traversing the first $k$ nodes of the trie.