To search, Click below search items.


All Published Papers Search Service


A Fast Multiple Pattern Matching Algorithm using Context Free Grammar and Tree Model


G.Phanindra, K.V.V.N. Ravi Shankar, P.Deepak Sreenivas


Vol. 7  No. 9  pp. 231-234


Multiple Substring-Pattern Matching Algorithm presented here is implemented in two phases. The first phase is preprocessing in which an n-ary tree like structure is constructed for the given text data and Griebach Normal Form is created for given Context Free Grammar. The second phase called search phase takes as input an n-ary tree structure and Griebach Normal Form of given Context free grammar constructed in phase 1 and outputs those strings that match both the text data and the context free grammar. The algorithm proposed here has the advantage that it can retrieve any number of patterns at the same time. This finds wide applications in Bio-informatics, information retrieval and requirements specification stage of software life cycle development.


Pattern Matching, preprocessing, n-ary tree, Context Free Grammar, Griebach Normal Form, Bio-informatics, information retrieval