AN IMPROVED PREFIX-FREE REGULAR-EXPRESSION MATCHING

作     者：Han, Yo-Sub 

作者机构：Yonsei Univ Dept Comp Sci Seoul 120794 South Korea 

出 版 物：《INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE》 (国际计算机科学基础杂志)

年 卷 期：2013年第24卷第5期

页      面：679-687页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Basic Science Research Program through NRF MEST [2010-0009168, 2012R1A1A2044562] 

主　　题：String pattern matching regular-expression matching prefix-free regular expressions 

摘      要：We revisit the regular-expression matching problem with respect to prefix-freeness of the pattern. It is known that a prefix-free pattern gives only a linear number of matching substrings in the size of an input text. We improve the previous algorithm and suggest an efficient algorithm that finds all pairs (start, end) of start and end positions of all matching substrings with a singles can of the input when the pattern is a prefix-free regular expression.