4
$\begingroup$

I'm practising solving programming problems. Here I have some problems:

We are given a directed graph $G$ with $n\le 100$ nodes and $m\le 1000$ edges, which edges are labelled (labels are also given) with words shorter than $1000$ characters. For a given word $s$ ($|s|\le 10^5$) decide if it exists a path (edge repetitions are allowed) $e_1,...,e_n$ in $G$, such that after we concatenate words from edges $e_1,...,e_n$ (in this order) we get the word $s$.

For example $n=3, m=4$ and edges: $1\xrightarrow{abc} 2, \ 2\xrightarrow{a} 1, \ 1\xrightarrow{aaa} 2, \ 2\xrightarrow{xyz} 3$, we can create word $abcaaaaxyz$

But for $n=2, \ m=3$ and edges: $1\xrightarrow{aa} 2, 2\xrightarrow{aa} 1, 1\xrightarrow{aa} 2$, we can't create the word $aaaaa$.

I was thinking about this problem for a long time and I don't know how to approach it. $G$ seems to be very small but every straight brute force solution will be of course too slow I think (comparing words, remembering states in recursive walking through $G$). I really want to know how to solve it. Can anyone help?

$\endgroup$
2
  • 1
    $\begingroup$ Hint: The class of such words is a regular language. $\endgroup$ Mar 9, 2013 at 18:10
  • $\begingroup$ @ThomasAndrews, right. Because they are accepted by finite-state machine, but I don't know how to use it. $\endgroup$
    – xan
    Mar 9, 2013 at 18:22

2 Answers 2

0
$\begingroup$

One (suboptimal) way is to keep an array of $\le m\cdot maxlen =1000000$ bits, where each bit stands for "The string so far can match up to character $i$ of edge-label $j$" and update this char by char of the input. The running time of $O(s\cdot m\cdot maxlen)$ may forbid this for practical applications though.

Better methods locate all positions where string $j$ occurs (completely) in the input (at runtime $O(maxlen+s)$, not $O(maxlen\cdot s)$!) and then use DP or e.g. a priorityqueue with memory $O(n\cdot maxlen)$ for final processing.

$\endgroup$
0
$\begingroup$

What kind of bruteforce you are talking about? What kind of complexity you were expecting? Is the following too slow for you?

Some random approach: create a graph $G'$ with $n\cdot s$ nodes where there is an edge between $(n_1,s_1)$ and $(n_2,s_2)$ when you can move from $n_1$ to $n_2$ by edge with a label $w$ such that $s_2 = s_1 + w$. Then go through all the edges and matching with some extension of KMP for multiple patterns create all the $m\cdot s$ edges. Finally, check if there is a path from the start to the end.

Edit: Just some clarification, I don't expect you to code this exactly as I described, because you would probably run out of memory. Instead of creating the graph off-line, hold only the reachability, that is a $\mathtt{bool}$ array of size $n \cdot s$ describing if the particular node is reachable (in fact the words are shorter than 1000 characters, so $n \cdot 1001$ should be enough). The graph should be created on-line, with $m$ parallel copies of KMP being evaluated lazily, that is you need to keep the $m$ states for each algorithm and move it one-by-one each time you proceed to the next character. When KMP for word $w$ of edge $(n_1,n_2)$ tells you that there is a match, and there is a reachability bit set for $(n_1,s_1)$ where $s_1$ is the current position, then you set the reachability bit for $(n_2,s_1+|w|)$.

I hope this helps ;-)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .