# Text Indexing for Regular Expression Matching
## 3 A Regular Expression Index
### Solution Graphs: Pattern Matching via Reachability
Second from the bottom: solution graph for \(a\circ b^{*}\). (**Bottom**): solution graph for \(b\circ a^{*}\). Lastly, we consider the **star** operator '\(*\)' operator. Again taking \(V_{1}\), \(V_{2}\) as the starting and ending vertex sets of \(G_{1}\) for \(p_{1}\), construct the solution graph \(G\) for \(p_{1}^{*}\) as follows:  
1. Graph \(G\) is initially equal to \(G_{1}\). 2. Add two sets of new vertices \(W_{1}=\{w_{1}^{1},\ldots,w_{|T|+1}^{1}\}\) and \(W_{2}=\{w_{1}^{2},\ldots,w_{|T|+1}^{2}\}\). These will be the start and end vertex sets, respectively, of \(G\). 3. Add the directed edges: \(\{(w_{1}^{1},w_{2}^{1})\ |\ 1\leq i\leq|T|+1\}\), \(\{(w_{1}^{1},v_{i}^{1})\ |\ 1\leq i\leq|T|+1\}\), \(\{(v_{i}^{2},v_{i}^{1})\ |\ 1\leq i<|T|+1\}\), and \(\{(v_{i}^{2},w_{i}^{2})\ |\ 1\leq i\leq|T|+1\}\). In each step above \(\Theta(|T|)\) edges are added to the resulting solution graph. Furthermore, any solution graphs that arise from matching a pattern consisting of only symbols (the leaves of the parse tree) have only \(O(|T|)\) edges. Therefore, a regular expression of length \(|p|\) results in a solution graph having \(O(|T||p|)\) edges. Lemma 3: _The constructions of \(G\) for the **or** (\(p_{2}|p_{2}\)), **concatenation** (\(p_{1}\circ p_{2}\)), and **star** (\(p_{1}^{*}\)) operators result in \(G\) being a solution graph for the corresponding regular expression._  
Proof: The first two of these are straight forward, but we include them for completeness. For the **or** operator, first consider when there exists a substring \(T[i,j]\) matched by \(p_{1}\mid p_{2}\). Then the substring \(T[i,j]\) must be matched by \(p_{1}\) or \(p_{2}\). Say WLOG it is matched by \(p_{1}\), then there exists a path from \(v_{i}^{1}\in V_{1}\) to \(v_{j+1}^{2}\in V_{2}\), which implies a path from \(w_{i}^{1}\in W_{1}\) to \(w_{j+1}^{2}\in W_{2}\) in \(G\) due to the edges \((w_{i}^{1},v_{i}^{1})\) and \((v_{j+1}^{2},w_{j+1}^{2})\). In the other direction, if there exists a path from \(w_{i}^{1}\) to \(w_{j+1}^{2}\), it must start with either the edge \((w_{i}^{1},v_{i}^{1})\) or \((w_{i}^{1},u_{i}^{1})\). Say WLOG it starts with the edge \((w_{i}^{1},v_{i}^{1})\), then the final edge must be \((v_{j+1}^{2},w_{j+1}^{2})\) since there no edges between the graphs \(G_{1}\) and \(G_{2}\). This implies a path through \(G_{1}\) from \(v_{i}^{1}\) to \(v_{j+1}^{2}\) and hence the substring \(T[i,j]\) is matched by \(p_{1}\). (ii) For **concatenation**, first consider when there exists a substring \(T[i,j]\) matched by \(p_{1}\circ p_{2}\). Then there exists some \(k\) such that \(i\leq k\leq j\) where \(T[i,k-1]\) is matched by \(p_{1}\) and \(T[k,j]\) is matched by \(p_{2}\). Hence, there exists a path from \(v_{i}^{1}\) to \(v_{k}^{2}\) in \(G_{1}\) and a path from \(u_{k}^{1}\) to \(u_{j+1}^{2}\) in \(G_{2}\). Connecting these paths using the edge \((v_{k}^{2},u_{k}^{1})\) we obtain the desired path. In the other direction, if there exists a path from \(v_{i}^{1}\) to \(u_{j+1}^{2}\) then there must exist a path from \(v_{i}^{1}\) to some \(v_{k}^{2}\) and then a path from \(u_{k}^{1}\) to \(u_{j+1}^{2}\), which implies \(T[i,k-1]\) is matched by \(p_{1}\) and \(T[k,j]\) is matched by \(p_{2}\). (iii) For the **star** operator, Figure 2 is particularly helpfully in understanding the argument. We will use induction on \(x\) to show that all substrings \(T[i,j]\) matched by \(x\geq 1\) concatenations of \(p_{1}\) correspond to a path from \(v_{i}^{1}\) to \(v_{j+1}^{2}\). Suppose \(T[i,j]\) is matched by \(p_{1}^{x}\). If \(x=1\), then by the definition of \(G_{1}\), there exists a path from \(v_{i}^{1}\) to \(v_{j+1}^{2}\). For \(x>1\), we assume our inductive hypothesis holds for all substrings of \(T\) matched by \(x-1\) concatenations of \(p_{1}\). Since \(T[i,j]\) matches \(p_{1}^{x}\), there exists an index \(k<j\) such that \(p_{1}^{x-1}\) matches \(T[i,k]\). Additionally, the substring \(T[k+1,j]\) is matched by \(p_{1}\).