Pattern Matching with Flexible Wildcards and Recurring Characters

Pattern matching is an important task, which is widely used in many fields, such as information retrieval and bioinformatics. Recently, a much more flexible pattern matching problem with wildcards has been proposed. Chen et al. introduced local constraints, global constraints and the one-off condition into the task of pattern matching, and the most representative algorithm SAIL was designed. However, the performance of SAIL is not analyzed well, which affects its application. Therefore, this paper analyzes the performance of SAIL in-depth, and discovers that the matching result is closely related to the features of patterns. Meanwhile, the completeness of SAIL in the pattern matching with no-recurring characters is proved, and an improved algorithm, named RSAIL, is proposed for pattern matching with recurring tail characters. Extensive experiments demonstrate that RSAIL improves the number of matches by 2.2% compared to SAIL.