New Algorithms for Regular Expression Matching
New Algorithms for Regular Expression Matching
复制标题
正则表达式匹配的新算法
DOI：
10.1007/11786986_56
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Philip Bille
中科院分区：
文献类型：
--
作者：
Philip Bille
在本文中，我们重新审视经典的正则表达式匹配问题，即，给定一个正则表达式R和一个字符串Q组成的m和n个符号，分别，决定是否Q匹配R指定的字符串之一。我们提出了新的算法设计的一个标准的单位成本RAM的字长w ≥logn。我们改进了使用O（m）空间的算法的最佳已知时间界限，并且只要w ≥log2n，我们就获得了已知最快的算法，而不管使用了多少空间。
In this paper we revisit the classical regular expression matching problem, namely, given a regular expression R and a string Q consisting of m and n symbols, respectively, decide if Q matches one of the strings specified by R. We present new algorithms designed for a standard unit-cost RAM with word length w ≥logn. We improve the best known time bounds for algorithms that use O(m) space, and whenever w ≥log2n, we obtain the fastest known algorithms, regardless of how much space is used.