I have a tricky problem, look:$n, \le 100, m\le 1000 $ where $m$ is number of edges and $n$ is number of nodes.On every directed edge there is word $w$ such that $|w| \le 1000$.  There is given one word $s$ ($|s|\le 100000$). Our task is asnwer to question:Is there transition in this graph such that we build this word $s$ ?Look at example: answer: YESCould you help me ?
find path in directed graph according to word
graphs
Let me explain the basics of the solution without details.Define $T[u,i]$ as Is it possible to make $s[1..i]$ when I am at vertex $u$?.Obviously for all $u$, $T[u, 0] = true$.If there is an edge from vertex $u$ to vertex $v$ and the word on the edge matches with $s[i+1..j]$ and $T[u, i] = true$, we can infer that $T[v, j]$ is also $true$.So you can repeatedly do this process and calculate $T$ for all $u$ and $i$. If $T[x, |s|] = true$ for some $x$, we can make the word!