Prefix-free regular languages and pattern matching

作     者：Han, Yo-Sub Wang, Yajun Wood, Derick 

作者机构：Korea Inst Sci & Technol Intelligence & Interact Res Ctr Seoul 130650 South Korea Hong Kong Univ Sci & Technol Dept Comp Sci Kowloon Hong Kong Peoples R China 

出 版 物：《THEORETICAL COMPUTER SCIENCE》 (理论计算机科学)

年 卷 期：2007年第389卷第1-2期

页      面：307-317页

核心收录：

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

基　　金：Research Grants Council, University Grants Committee, RGC, UGC, (HKUST6197/01E) Korea Institute of Science and Technology, KIST, (HKUST6206/02E) 

主　　题：string pattern matching regular-expression matching prefix-free regular languages pruned prefix-free languages 

摘      要：We explore the, regular-expression matching problem with respect to prefix-freeness of the pattern. We prove that a prefix-free regular expression gives only a 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. (c) 2007 Elsevier B.V. All rights reserved.