The exact string matching is essential in application areas such as Bioinformatics and Intrusion Detection Systems. Speeding-up the string matching algorithm will therefore result in accelerating the searching process in DNA and binary data. Previously, there are two types of fast algorithms exist, bit-parallel based algorithms and hashing algorithms. The bit-parallel based are efficient when dealing with patterns of short lengths, less than 64, but slow on long patterns. On the other hand, hashing algorithms have optimal sublinear average case on large alphabets and long patterns, but the efficiency not so good on small alphabet such as DNA and binary texts. In this paper, the authors present hybrid algorithm to overcome the shortcomings of those previous algorithms. The proposed algorithm is based on q-gram hashing with guaranteeing the maximal shift in advance. Experimental results on random and complete human genome confirm that the proposed algorithm is efficient on various pattern lengths and small alphabet.
Top1. Introduction
The problem of finding the occurrences of a predefined pattern in big data or very long sequences is classical problem in computer science and it has been studied intensively by researchers due to the growing of data which are produced day-by-day. There are many applications that depend on the pattern matching, e.g., biological sequences which are produced every day by high throughput sequencing technologies (Morozova & Marra, 2008), natural language processing, or retrieving a specific data from very large databases. Bioinformatics is one of the fields where the pattern matching problem is used widely to search for specific pattern exactly or approximately (Barton, Iliopoulos, & Pissis, 2014; Simone Faro & Lecroq, 2009a; S. Faro & Lecroq, 2012; Kalsi, Peltola, & Tarhio, 2008) where the DNA is considered as a string and the four symbols A, C, G, and T, represent the four nucleotides Adenine, Cytosine, Guanine, and Thymine, respectively. Computer networks is the other area where this problem is applied. The binary string matching used in the intrusion detection systems to detect malwares within the heavy load traffic and searching IP addresses in routers swiftly (Chu, Huang, Tsai, & Hsieh, 2008; Liu, Huang, Chen, & Kao, 2004; Tuck, Sherwood, Calder, & Varghese, 2004).
The importance of speeding-up the searching process stems from that there is a need to find the occurrences of a particular pattern and whether the pattern exist or not in terabytes of data. Searching such amount of data offline by uploading the data to memory is not possible due to the memory limitations. In computer networks, Antiviruses are installed on routers or personal computers for detecting malwares so speeding-up the inspecting process increases the performance of the systems.
The problem is formulated as follows. Given a string T of length n and a pattern P of length m, the problem is to find the number of repetitions of P in T. In practice 
. Let Σ denotes the set of symbols, then Σ* denotes the language from which the pattern and the text are drawn and we write P,T∈Σ*.
Two types of alphabets are considered in this paper, the DNA alphabet, Σ={A,C,G,T}, and binary alphabet, Σ={0,1}. The text and the pattern are represented by arrays of one dimension and the two arrays are indexed starting from 0. We say that the pattern P occurs in the text T, if P[i]=T[j‑m+i+1] where 0≤i<m and ∃j such that m‑1≤j<n.