String Matching
Brute force string search algorithm
An algorithm to find a string within another string by trying each position one at a time.
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
- Comparison can be done in any order
- 2n expected text characters comparisons.
- The brute force algorithm consists in checking, at all positions in the text between 0 and n-m.
- The time complexity of this search phase is O (mn)
- The expected number of text character comparisons is 2n.
Markov algorithm
Also known as the “ normal algorithm “ , Developed by the Russian mathematician A.A. Markov.
- Markov algorithm consists of a sequence of pairs – antecedents and consequents.
- They are to be tied in the strict priority of the order in which they are listed , and the current rule is applied if the string under transformation contain s the antecedent as the substring ; that being the case , the substring found is replaced with the consequent.
- A markov algorithm is a string rewriting system that uses grammar like rules to operate on the strings of symbols.
String Matching Algorithm
TECHIE MASH 