String Matching
DEFINITION The problem of finding occurrence (s) of a pattern string within another string or body of text. There are many different algorithms for efficient searching.
Brute Force String Search Algorithm
Definition An algorithm to find a string within string or body of text by trying each position one at a time. There are many far faster string matching algorithms.
Also known as naïve string search.
Main features
No preprocessing phase;
Constant extra space needed
Always shifts the window by exactly 1 position to the right
Comparisons can be done in any order ;
Searching phase in 0 (mm) time complexity ;
2n expected text characters comparisons.
The brute force algorithm consists in checking, at all positions in the text between 0 and n-m whether an occurrence of the pattern starts there or not. Then, after each attempt it shifts the pattern by exactly one position to the right.
The brute force algorithm requires no preprocessing phase and a constant extra space in addition to the pattern and the text. During the searching phase the text character comparisons can be done in any order. The time complexity of this searching phase is o (mn) (when searching for am-1b in an for instance). The expected number of text character comparisons is 2n.
Data Structure & Algorithms Assignment Help, Live Experts
Struggling with data structure problems? Data structure subject is quite tough to learn? Need quick assistance in data structure questions? ExpertsMind.com is right place for you where your search ends, We at ExpertsMind offer online data structure assignment help, data structure homework help and data structure and algorithms question's answers by best online support by qualified tutors.
ExpertsMind.com - String Matching Assignment Help, String Matching Homework Help, String Matching Assignment Tutors, String Matching Solutions, String Matching Answers, An introduction to data structures Assignment Tutors