TAILIEUCHUNG - A new approach to exact pattern matching

In this paper we introduce a flexible approach to design an effective algorithm for exact pattern matching, and compare it with some of the most efficient algorithms, such as AOSO, EBOM, FJS, FSBNDM, HASHq, LBNDM, SA, BMH-SBNDM, SBNDMq, TVSBS. These results are based on the concept of the degree of fuzziness (appearance) presented by P. T. Huy et al. in 2002. | Journal of Computer Science and Cybernetics 2019 197-216 DOI 1813-9663 35 3 13496 A NEW APPROACH TO EXACT PATTERN MATCHING NGUYEN HUY TRUONG School of Applied Mathematics and Informatics Hanoi University of Science and Technology Vietnam Crossref Similarity Check Powered w ITheritlMte Abstract. In this paper we introduce a flexible approach to design an effective algorithm for exact pattern matching and compare it with some of the most efficient algorithms such as AOSO EBOM FJS FSBNDM HASHq LBNDM SA BMH-SBNDM SBNDMq TVSBS. These results are based on the concept of the degree of fuzziness appearance presented by P. T. Huy et al. in 2002. Theoretical analyses and experimental results indicate that in practice our proposed algorithm is faster than the above mentioned algorithms in most of the cases of patterns and alphabets. Keywords. Exact Pattern Matching String Matching Automata Approach. 1. INTRODUCTION Pattern matching is a classic problem in computer science and one of the most cited problems in word processing algorithms. The applications of pattern matching algorithms are used daily to access information such as in the search engine Google database queries search and replace in text editing systems etc. At present there are two research directions for the problem that are exact and approximate pattern matching. Moreover based on the number of patterns found by the algorithm the pattern matching problem can be divided into single and multiple pattern matching. Our work addresses the exact single pattern matching problem hereafter commonly called the exact pattern matching problem . Given a pattern string x of length m and a text y of length n on the same alphabet. The exact pattern matching problem is to search for occurrences of the pattern x in the text y. Since 1977 with the two famous publications of the Boyer-Moore 6 and Knuth-Morris-Pratt 18 exact pattern matching algorithms there have been about hundreds if

• Toán học
• Exact pattern matching
• String matching
• Automata approach
• Degree of fuzziness
• Proposed algorithm
• Oretical analyses
• BMC Bioinformatics
• RNA bioinformatics
• Structure based comparison of RNA
• Identifying sequence structure motifs
• Massive transcription