I am trying to understand Boyer Moore algorithm & KMP algorithm (Knuth Morris Pratt)? I tried some places like GeeksForGeeks, TutorialsPoint etc. But I have still some doubts. If you guys have some resources or videos where these algorithms are explained in somewhat simple terms, please share them. First I am trying to understand the logic behind these algorithms clearly. Then I will go to code implementation.
midyajai 0 Newbie Poster
rproffitt 2,662 "Nothing to see here." Moderator
I read the Wikipedia on this and came back that I would not code this at all but use the search calls/APIs that are currently in whatever language I'm coding in now. If I felt one method was better than the next I would test it using each supplied search against a few test sets and be done with it by days end.
Maybe there's some homework assignment here but that was not told.
midyajai 0 Newbie Poster
I am a student. I am trying to learn these two algorithms. I am not looking for ready-made apis to get the job done. That is the problem, I can't skip it.
rproffitt 2,662 "Nothing to see here." Moderator
Did you read the Wikipedia on these. I read one at least if not more and felt they did an excellent job of explaining how they work.
But understanding how they work may not give a beginning programmer all they need to know to "code it up." Remember you didn't reveal this is homework as well as what the assignment was. Imagine the poor student that was assigned yet another Time Complexity piece of homework but wrote what you did and left out what they really needed to do. Nod to https://en.wikipedia.org/wiki/Time_complexity
As to learn these two algorithms, in all the classes I took over the year the algorithms were in the text that was part of the course. Today we can supplement that with the web but did the prof forget to supply "source material"?
zoukmaz 0 Newbie Poster
You need to keep searching & read articles/watch videos till you find something that clicks for you. There are lot of resources out there. And different resources might be useful for different people from various backgrounds. Anyways, this is one of the resources that say KMP can be explained in plain english https://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html :) . I took a quick look & I think it is simple enough. Now its upto you whether you find it useful or not. Otherwise, keep searching.
midyajai 0 Newbie Poster
Thank you for sharing KMP link. I also got somewhat good grasp on Booyer Moore. Now I will try to implement them in code.
Alisha_8 34 Newbie Poster
Sure! I can provide you with some resources that explain the Boyer Moore algorithm and the Knuth Morris Pratt (KMP) algorithm in a simple and clear manner. Here are a few sources you can check out:
-
InterviewBit Blog - KMP Algorithm:
This blog post provides a detailed explanation of the KMP algorithm, along with code implementations in multiple programming languages. You can find it at:
KMP Algorithm - InterviewBit Blog -
Topcoder Tutorial - String Searching Algorithms:
This tutorial covers both the Boyer Moore and KMP algorithms, along with explanations and code examples. It also compares the two algorithms and discusses their time complexities.
Link: String Searching Algorithms - Topcoder Tutorial -
YouTube Video - KMP Algorithm by Tushar Roy:
Tushar Roy's YouTube channel offers a comprehensive video tutorial on the KMP algorithm. The video explains the algorithm's logic and demonstrates its implementation using visualizations.
Link: KMP Algorithm Tutorial by Tushar Roy
These resources should help you understand the logic behind both the Boyer Moore and KMP algorithms. Once you grasp the concepts, you can proceed to the code implementation.
Be a part of the DaniWeb community
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.