HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Naive Pattern Matching:
Algorithm Analysis:
- The Naive pattern matching algorithm takes O((n-m+1)*m) executions for a given m in the worst case as the pattern P[m] is shifted n-m+1 times and for each shift m letters are compared. To calculate the length of m for a worst case performance of the algorithm we have Hence the worst case performance of the algorithm results when m = n/2 and the match occus at n-m+1 place. Hence worst case performance of O(m^2).
- Information gathered (i.e. the subpattern(s) matched so far) when matching letters at a particular position is discarded as a mismatch occurs. This information is lost and hence the algorithm is generally considered inefficient.
Maintainer: rakesh.mawa@hsc.com
Categories: PatternMatching Software
<< Main.PatternMatching | PatternMatching-Trail | Main.PatternMatching-FiniteAutomata >>
Comments
