# Order-Preserving Multiple Pattern Matching in Parallel
## 2 Related Works  
Given string \(x\), the length of \(x\) is denoted by \(|x|\) and the \(i\)-th character of \(x\)\((1\leq i\leq|x|)\) is denoted by \(x[i]\). The substring from \(x[i]\) to \(x[j]\) is denoted by \(x[i..j]\)\((1\leq i\leq j\leq|x|)\). \(x[1..i]\) is called a prefix of \(x\) and \(x[i..|x|]\) is called a suffix of \(x\) for \(1\leq i\leq|x|\). For convenience, we assume that all the characters in the string are different. Given two strings \(x\), \(y\)\((|x|=|y|)\), if \(x[i]<x[j]\Leftrightarrow y[i]<y[j](1\leq i,j\leq|x|)\) is satisfied, and \(x\) and \(y\) are order-isomorphic and denoted by \(x\approx y\)[1,4,10].  
Let \(x^{\prime}\) be the string constructed by sorting all the characters of \(x\) in ascending order. Then, the position table \(POS_{x}\) of \(x\) is defined as follows:  
\[POS_{x}[i]=j(x^{\prime}[i]=x[j],1\leq i\leq|x|).\]  
That is, \(POS_{x}[i]\) is the index of the \(i\)-th smallest character in \(x\). Given two strings \(x,y\)\((|x|=|y|)\), for all \(i(1\leq i<n)\), if \(y[POS_{x}[i]]\leq y[POS_{x}[i+1]]\) is satisfied, \(x\approx y\)[8]. A prefix table \(\mu_{x}\) of string \(x\) is defined as follows:  
\[\mu_{x}[i]=|\{j:x[j]<x[i],1\leq j<i\}|+1.\]  
That is, \(\mu_{x}[i]\) represents the number of characters that are smaller than \(x[i]\) in \(x[1..i]\). If the prefix tables of two strings \(x\) and \(y\) are the same, that is, \(\mu_{x}=\mu_{y}\), \(x\approx y\)[1]. Note that when there exist the same characters in the given string, order-isomorphism can still be determined using the extended prefix representation proposed in [2]. Table 1 presents the prefix table \(\mu_{x}\) and position table \(POS_{x}\) when \(x=(23,29,20,57,59)\).  
In [7], an OPMPM algorithm was proposed using fingerprints of \(q\)-grams. The fingerprint converts a \(q\)-gram (a string of length \(q\)) into an integer within the range of \([1,q!]\) using the factorial number system [11,12]. The fingerprints are used to find candidate substrings of text \(T\) that may be order-isomorphic to pattern \(P\). Given a \(q\)-gram \(x\), fingerprint \(f(x)\) is defined as follows [3,7]:  
\[f(x)=\sum_{k=1}^{q}[(\mu_{x}[k]-1)\times(k-1)!]+1.\]  
For example, if \(q\)-gram \(x=(8,10,6)\), \(f(x)=2\).  
In [1], the Aho-Corasick automaton [6] is used to solve the order-preserving multiple pattern matching problem. In the preprocessing phase, the Aho-Corasick automaton is created in \(O(M\log\overline{m})\) time using a set of prefix tables of patterns. In each Step \(i(1\leq i\leq n)\) of the search phase, the state for \(T[i]\) is computed and \(P_{a}(1\leq a\leq k)\) is searched in the  
\begin{table}
\begin{tabular}{c c c c c c} \hline \(x\) & 23 & 29 & 20 & 57 & 59 \\ \(\mu_{x}[i]\) & 1 & 2 & 1 & 4 & 5 \\ \(POS_{x}[i]\) & 3 & 1 & 2 & 4 & 5 \\ \hline \end{tabular}
\end{table}
Table 1: Prefix table and position table of \(x=(23,29,20,57,59)\).  
automaton using the transition function, the failure function, and the output function of the automaton. Figure 1 shows the Aho-Corasick automaton when \(P_{1}=(17,25,15,30)\), \(P_{2}=(30,44,25,40)\), and \(P_{3}=(40,50,61)\).  
Let \(\tilde{P}_{a}(1\leq a\leq k)\) be the prefix of length \(m\) for each pattern \(P_{a}\) and let \(\tilde{\mathbb{P}}=\{\tilde{P}_{1},\tilde{P}_{2},\ldots,\tilde{P}_{k}\}\). [PERSON] et al. [8] proposed an OPMPM algorithm that generates the position table \(POS_{P_{a}}\) for each \(P_{a}(1\leq a\leq k)\) and the fingerprint table \(FP_{a}\) that stores the rightmost \(q\)-gram's fingerprint of \(\tilde{P}_{a}(1\leq a\leq k)\) in the preprocessing phase, to find candidate patterns that may be order-isomorphic to substrings of \(T\). In the search phase, all substrings of \(T\), which are order-isomorphic to any \(P_{a}(1\leq a\leq k)\), are searched using \(FP_{a}\) and \(POS_{P_{a}}\).