Abstract
We explore the regular-expression matching problem with respect to prefix-freeness of the pattern. We show that the prefix-free regular expression gives only linear number of matching substrings in the size of a given text. Based on this observation, we propose an efficient algorithm for the prefix-free regular-expression matching problem. Furthermore, we suggest an algorithm to determine whether or not a given regular language is prefix-free.
Han and Wood were supported under the Research Grants Council of Hong Kong Competitive Earmarked Research Grant HKUST6197/01E and Wang was supported under the Research Grants Council of Hong Kong Competitive Earmarked Research Grant HKUST6206/02E.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aho, A.: Algorithms for finding patterns in strings. In: van Leeuwen, J. (ed.) Algorithms and Complexity. Handbook of Theoretical Computer Science, vol. A, pp. 255–300. The MIT Press, Cambridge (1990)
Aho, A., Corasick, M.: Efficient string matching: An aid to bibliographic search. Communications of the ACM 18, 333–340 (1975)
Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Communications of the ACM 20(10), 762–772 (1977)
Clarke, C.L.A., Cormack, G.V.: On the use of regular expressions for searching text. ACM Transactions on Programming Languages and Systems 19(3), 413–426 (1997)
Crochemore, M., Hancart, C.: Automata for matching patterns. In: Rozenberg, G., Salomaa, A. (eds.) Linear modeling: background and application. Handbook of Formal Languages, vol. 2, pp. 399–462. Springer, Heidelberg (1997)
Giammarresi, D., Montalbano, R.: Deterministic generalized automata. Theoretical Computer Science 215, 191–208 (1999)
Han, Y.-S., Wood, D.: The generalization of generalized automata: Expression automata. In: Domaratzki, M., Okhotin, A., Salomaa, K., Yu, S. (eds.) CIAA 2004. LNCS, vol. 3317, pp. 156–166. Springer, Heidelberg (2005)
Hopcroft, J., Ullman, J.: Formal Languages and Their Relationship to Automata. Addison-Wesley, Reading (1969)
Knuth, D., Morris Jr., J., Pratt, V.: Fast pattern matching in strings. SIAM Journal on Computing 6, 323–350 (1977)
Myers, E.W., Oliva, P., Guimãraes, K.S.: Reporting exact and approximate regular expression matches. In: Farach-Colton, M. (ed.) CPM 1998. LNCS, vol. 1448, pp. 91–103. Springer, Heidelberg (1998)
Thompson, K.: Regular expression search algorithm. Communications of the ACM 11, 419–422 (1968)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Han, YS., Wang, Y., Wood, D. (2005). Prefix-Free Regular-Expression Matching. In: Apostolico, A., Crochemore, M., Park, K. (eds) Combinatorial Pattern Matching. CPM 2005. Lecture Notes in Computer Science, vol 3537. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11496656_26
Download citation
DOI: https://doi.org/10.1007/11496656_26
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26201-5
Online ISBN: 978-3-540-31562-9
eBook Packages: Computer ScienceComputer Science (R0)