# Text Indexing for Regular Expression Matching
## 1 Introduction
### Background and Related Work  
A regular expression \(p\) as defined in this paper is one of the following: the or operator '\(|\)' applied to two regular expressions \(p_{1}\) and \(p_{2}\), the **concatenation** operator '\(\circ\)' applied to two regular expressions \(p_{1}\) and \(p_{2}\), the **star** operator '\(\ast\)'' applied to a regular expression \(p_{1}\), a symbol from the alphabet, the empty string, or the empty set. We call \(p_{1}\) and \(p_{2}\) subexpressions of \(p\). We will not consider more advanced operators such as bracketed expressions that allow for a range of characters to be denoted within a few symbols, or captured groups that allow matched substrings to be recalled, or other added features that can make the problem NP-complete [23]. When considering the length of \(p\), denoted \(|p|\), one can view this as the number of vertices in the parse tree for \(p\), as seen in Figure 1. The precedence-setting braces in the regular expression do not contribute to its length as they do not appear as any vertex in the parse tree. To avoid confusion, we will always refer to the length of the text \(T\) as \(|T|\) and the length of the pattern as \(|p|\), thereby reserving \(n\) for the \(n\times n\) matrices in Section 2. We will also always consider \(T\) as indexed from \(1\) to \(|T|\).  
As mentioned in the introduction, this problem has to be solved frequently in applications. As such, different heuristics have been proposed [24; 25]. Most of these heuristics use the idea of multi-grams. Multi-grams are small portions of text that will match some part of a substring in the inputted expression. In practice, applications often use multi-grams. Furthermore, to the author's best knowledge, there are no solutions that preprocess the \(T\) and have a guaranteed time complexity less than that of any algorithmic solution. In the case where the pattern is given for preprocessing (rather than the text) work by [PERSON] shows that after \(O(|p|\log|p|)\) preprocessing time, each character in the text can be processed in \(O(|p|\frac{\log w}{w}+\log|p|)\) time, where \(w\) is the word size [26].  
For the algorithmic problem without any preprocessing, there exists a large body of research. The oldest and most fundamental solution is Thompson's Method from 1968 [27]. This method locates substrings matching the regular expression \(p\) in \(O(|T||p|)\) time via the simulation of a nondeterministic finite automaton equivalent to \(p\). Results by [PERSON] improve this to \(O(\frac{|T||p|}{\log|T|}+(|T|+|p|)\log|T|)\) time [28]. This was further improved to \(O(\frac{|T||p|\log\log|T|}{\log^{15}|T|}+|T|+|p|)\) time in [29]. Additionally, a result by [PERSON] and [PERSON] says that if \(p\) consists of \(k\) strings then the algorithmic problem can be solved in time \(O(|T|k+|p|\log k)\)[30]. In practice, for programming languages like Perl and Python, the simulation of this NFA is typically done using a method called back-tracking, which can lead to exponential time in the worst case. The main reason for this choice in implementation appears to be its simplicity [31].  
To help answer why there have not been more significant advancements on the algorithmic problem, [PERSON] and [PERSON] established fine-grained lower bounds [13]. These lower bounds use the Strong Exponential Time Hypothesis (SETH). The proofs use a reduction from SETH to the problem of finding two orthogonal vectors, each from its own set (the Orthogonal Vectors problem). This is then reduced to pattern matching on regular expressions. The main idea in the final step is to use regular expressions to detect orthogonality between two vectors. The same technique is used in this paper in Section 2, although conditioned on a different conjecture. Both the work [13], as well as extensions of this work [32], focus on classifying regular expressions based on which types make pattern matching more difficult. We do not make such distinctions here.