New Algorithms for Regular Expression Matching TeX Export

@misc{citeulike:715660, abstract = {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} <br />O(n\frac{m \log w}{w} + m \log w) \&amp; \text{if \$m \&gt; w\$} \\ <br />O(n\log m + m\log m) \&amp; \text{if \$\sqrt{w} \&lt; m \leq w\$} \\ <br />O(\min(n+ m^2, n\log m + m\log m)) \&amp; \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.}, archivePrefix = {arXiv}, author = {Bille, Philip}, citeulike-article-id = {715660}, citeulike-linkout-0 = {http://arxiv.org/abs/cs.DS/0606116}, citeulike-linkout-1 = {http://arxiv.org/pdf/cs.DS/0606116}, day = {28}, eprint = {cs.DS/0606116}, keywords = {algorithmes, expression, rgulire, string-matching}, month = {Jun}, posted-at = {2006-07-19 15:24:19}, priority = {2}, title = {New Algorithms for Regular Expression Matching}, url = {http://arxiv.org/abs/cs.DS/0606116}, year = {2006} }

TY - ELEC ID - citeulike:715660 L3 - citeulike-article-id:715660 N2 - 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} <br />O(n\frac{m \log w}{w} + m \log w) &amp; \text{if $m &gt; w$} \\ <br />O(n\log m + m\log m) &amp; \text{if $\sqrt{w} &lt; m \leq w$} \\ <br />O(\min(n+ m^2, n\log m + m\log m)) &amp; \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. TI - New Algorithms for Regular Expression Matching KW - algorithmes KW - expression KW - rgulire KW - string-matching AU - Bille, Philip PY - 2006/Jun/28/ UR - http://arxiv.org/abs/cs.DS/0606116 ER -