From b446d37d892a78c44fbde479d805e7f062b8df3a Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 14 Oct 2021 16:56:18 +0200 Subject: Reword and add notes --- mgr.tex | 17 +++++++++++------ 1 file changed, 11 insertions(+), 6 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index e88115c..215540a 100644 --- a/mgr.tex +++ b/mgr.tex @@ -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} -- cgit v1.2.3