Naive String Matching Algorithm

Hi, this is Shubham Mishra. I write blogs on algorithms and new technologies. In today's blog, we will be going to see a traditional way for string matching. For this blog, I have taken the reference of Analysis of Algorithm by A.A.Putambekar's book. String matching generally used in text processing. Normally text processing is done in the compilation of a program. The string matching is a vital part in software designing and system designing. String matching means finding one or more generally all the occurrences of a string in a text. These occurrences are called Pattern.

Let,
Text T is denoted by T0.....T(n-1) and pattern P is denoted by P0....P(m-1).


String Matching Algorithm - Shubham Mishra
String Matching Algorithm



For String matching scenario we will be discussing many algorithms in upcoming blogs such as,

  1. The naive method (This blog)
  2. Rabin-Karp algorithm
  3. Finite automaton for string matching
  4. Knuth - Morris - Pratt method


Naive String Matching Algorithm

Naive string matching algorithm is a simplest among all string matching algorithm. It uses Brute Force approach. The brute force is a straightforward approach to solving the problem. This algorithm performs checking at all positions in the text between 0th to (n-m) position, whether an occurrence of the pattern start there or not. Then after each attempt, it shifts the position by one point in the right side. If there is any match then it returns else it continues for matching by shifting one position in the right. The drawback of this straightforward approach is that we have to do 'n' comparisons. Lets now understand the naive matching algorithm, consider an example below.


Naive String Matching Algorithm - Shubham Mishra
Naive String Matching Algorithm



Hence it returns the 'D' characters index of the Text string. Now, let's look in the algorithm,

Algorithm

Done with the Naive string matching algorithm. Even this algorithm is the simplest one but due to its high computation requirement, it is the worst choice to be selected for the string matching algorithm. Hence we will see another efficient algorithm in my next post.
See my all posts Shubham Mishra

Ok great, we are done with this post,  

Now if you like my way of talk, lets explore more blogs written by me and my inner knowledge,

Get to know answers for common search on Google : A blog for posts which can help you for daily life problems, such as where to get free images, Topic suggestion for the blog.

Computer Science algorithms and other knowledge share : A blog for posts such as best search algorithm, Top interview questions for diffrent technologies, knowledge share for some frameworks or programming languages for the interview or in general terms.

My ideas to solve real world problems : A blog where me shared and presented my ideas to solve a real world problems, this will be interesting for me.

Future of computer science technology discussed : A blog where me discussed about the future of computer science and new technologies which will change our way for looking to solve problems.

Ruby on Rails Web development Blog : As the name suggest, it is the blog for sharing few knowledge about RoR web development framework.


Liked my blogs, wanna to connect:

LinkedIn  |  GitHub  |  HackerEarth  |  ResearchGate  |  Twitter  |  Facebook  |  StackOverflow

Thanks for reading this post, Have a good day :)

<- Merge Sort Algorithm
Radix Sort algorithm ->




  

Comments

Post a Comment

Popular posts from this blog

Amazon Interview question from leetcode coding problem 1

Hi, This is  Shubham Mishra  from India,  this is the part of  Ruby on Rails  exploration journey.  In this post we will discuss about the leetcode problem and its both worst and best case solution asked in Amazon interview process and I am sure you will get excited to make your hands dirty with those code, so why to wait let's get started... Problem Statement: Return the indices of the two numbers such that they add up to target given an array of integers nums and an integer target. You may presume that each input would have exactly one solution, and you may not use the same element twice. The input array nums can be assumed to not be sorted, but you are free to return the solution in any order. Example: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: nums[0] + nums[1] = 2 + 7 = 9, so [0, 1] is the correct answer. Here is the function signature in Python to help you get started: The problem is to find two indices in an array of integers nums whose cor
Read more

Puzzles for the interview which every one should read once

Hi, This is  Shubham Mishra  a ROR, iOS, Python developer,  this is the part of  Algorithm analysis  exploration journey.  In this post we will discuss about the Awesome puzzles that may be asked in the interview process, whether it may be for any position or the role. Even if not for the interview but still you will enjoy to solve the below puzzles. The opportunity to bring unique insight to solving business issues will give you an immense advantage over other applicants. Only with daily practice and continuous effort can these capacities be established. For me it's like intellectual training for solve puzzles. I do it on a regular basis, and have progressed equally over time. I 'm sharing some of the trickiest & head scratching questions I've experienced in my journey to help you attain the ability. Such questions were aimed at organisations such as Goldman Sachs, Amazon , Facebook, JP Morgan etc. The Bus Chaos Chaos in the bus. There is a bus with 100 seats numbered
Read more

Use ChatGPT for improve your coding quality

Image
Hi, This is  Shubham Mishra  from India,   In this post we will discuss about how to Use ChatGPT for improve your coding quality and I am sure you will get excited to make your hands dirty with those code, so why to wait let's get started... When first time i asked ChatGpt to write some script for me, I asked "Write a shell script to open multiple chrome windows with some url's", it was to my surprise that ChatGPT not only wrote the script it also tried to explain every line of code, you can check the script here : Shell script to open multiple chrome windows , so then onwards not only for writing script but also for reviewing some of my work related code I ask ChatGPT to review and rewrite me optimised code too. How can Chat GPT provide some general tips and best practices that developers can follow to write good code: 1. Follow coding standards and best practices: Consistency is key when it comes to writing good code. Follow established coding standards and bes
Read more