Computer Science – Data Structures and Algorithms
Scientific paper
2006-06-28
Computer Science
Data Structures and Algorithms
Scientific paper
In this paper we revisit the classical regular expression matching problem, namely, given a regular expression $R$ and a string $Q$, decide if $Q$ matches one of the strings specified by $R$. Let $m$ and $n$ be the length of $R$ and $Q$, respectively. On a standard unit-cost RAM with word length $w \geq \log n$, we show that the problem can be solved in $O(m)$ space with the following running times: \begin{equation*} \begin{cases} O(n\frac{m \log w}{w} + m \log w) & \text{if $m > w$} \\ O(n\log m + m\log m) & \text{if $\sqrt{w} < m \leq w$} \\ O(\min(n+ m^2, n\log m + m\log m)) & \text{if $m \leq \sqrt{w}$.} \end{cases} \end{equation*} This improves the best known time bound among algorithms using $O(m)$ space. Whenever $w \geq \log^2 n$ it improves all known time bounds regardless of how much space is used.
No associations
LandOfFree
New Algorithms for Regular Expression Matching does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Algorithms for Regular Expression Matching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Algorithms for Regular Expression Matching will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-535157