diff options
| -rw-r--r-- | mgr.tex | 17 |
1 files changed, 11 insertions, 6 deletions
@@ -632,9 +632,10 @@ consider the vertex $y.q$, the unique vertex here of color $c$. If it is in the same connected component as $x.q_0$ (which we check by comparing $\componenttable[x.q_0]$ with $\componenttable[y.q]$), we can immediately answer whether or not $A$ will accept the word on this path based on whether this state -is accepting. Since we have not changed connected components, there is a -single-color path from $x.q_0$ down to $y.q$ and $q$ is indeed the state $A$ -would have ended in after running on the word from $x$ down to $y$. +is accepting. If that is the case then we have not changed connected components, +thus there is a single-color path from $x.q_0$ down to $y.q$ and $q$ is indeed +the state $A$ would have ended in after running on the word given by the labels +from $x$ down to $y$. Otherwise, we need to jump down to a lower copy of $Q$. We can find the first such copy where the color on our path changes from $c$ to something lower by @@ -736,9 +737,11 @@ with holes, and individual vertices created according to the following rules: Note that in the last rule, both $v_l$ and $v_r$ will either themselves be elements of $W$ or will have descendants in $W$ in only one of their subtrees. -In the first case, we will have already handled them, otherwise we will handle +In the first case, we will have already handled them. Otherwise, we will handle them with a rule different than the last one, thus only one part will be added -to the partition for each of them. +to the partition for each of them. In particular, each element of $W$ will +contribute only a constant number of parts to the partition (one part if handled +with one of the first three rules, three parts if handled with the last one). To see that indeed, for example $v_l$, won't need to be handled with rule 4, if it wasn't in $W$ but had descendants from $W$ in both its subtrees, then $W$ @@ -770,7 +773,9 @@ This may be proved by a simple case analysis. Now, once $W$ has been sorted by in-order numbers, we can complete our computation in time $O(m)$. It is enough to walk through the list and issue LCA queries about successive pairs. By the lemma, the resulting set will indeed -contain LCAs for each pair in the set. +contain LCAs for each pair in the set. Note also that for each successive pair +we will have added at most one new vertex to the closure, thus the size of the +closure of $W$ is linear in $m$. \section{Computing root states of parts} |