World's most popular travel blog for travel bloggers.

find path in directed graph according to word

, , No Comments
Problem Detail: 

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: YES enter image description here

Could you help me ?

Asked By : M.Swe
Answered By : user1743455

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!

Best Answer from StackOverflow

Question Source :

3200 people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback