Finding All Occurrences of a Pattern by a Genetic Algorithm Based Divide-and-Conquer Method

The method of finding a sequence of characters, called the pattern, in another much longer sequence of characters, called the text, is known as pattern matching. Several pattern-matching algorithms exist, that locate all the positions where a pattern occurs in a text. In this paper we have presented...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computer applications 2013-01, Vol.64 (18), p.48-52
Main Authors: Banerjee, Sagnik, Chakrabarti, Tamal, Sinha, Devadatta
Format: Article
Language:English
Subjects:
Algorithms
Division
Genetic algorithms
Matching
Texts
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The method of finding a sequence of characters, called the pattern, in another much longer sequence of characters, called the text, is known as pattern matching. Several pattern-matching algorithms exist, that locate all the positions where a pattern occurs in a text. In this paper we have presented an algorithm which implements a divide and conquer technique, which divides the text in smaller independent sub-texts and then looks for the existence of the pattern in each such sub-text. The said divide and conquer method thus eventually finds all the occurrences of the pattern in the given text. The points of division have been chosen using a genetic algorithm.
ISSN:0975-8887
0975-8887
DOI:10.5120/10737-5614