• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Junilu Lacar
Sheriffs:
  • Rob Spoor
  • Liutauras Vilda
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Piet Souris
  • Tim Holloway
  • Jj Roberts
  • Stephan van Hulst
Bartenders:
  • Himai Minh
  • Carey Brown
  • Frits Walraven

KMP Algorithm For Dummies

 
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am trying to understand KMP algorithm ( Knuth Morris Pratt ) for pattern searching. I understand it is not a simple algorithm. But can I get some tutorial for beginners? I went through several resources, but those made me more confused . I am looking for a explanation for novices & with less technical terms I guess. It is really hard to understand the time complexity of this algo.
 
Marshal
Posts: 73322
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

Please show us which links you tried and what it was you found especially difficult to understand.

Moving to a different forum; too general for this forum.
 
dhara das
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
https://www.geeksforgeeks.org/kmp-algorithm-for-pattern-searching/
https://www.tutorialspoint.com/Knuth-Morris-Pratt-Algorithm

https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

The above are some of the links I have tried, but I am not able to understand why search complexity is linear. I am looking for something which is intuitive.
 
Campbell Ritchie
Marshal
Posts: 73322
332
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I looked at that Wikipedia link myself. I can't remember exactly how it works.

The time complexity is linear because the algorithm records where a discrepancy occurred. It is then not necessary to start searching where we left off, but to start beyond the first error. If you started one character on from the previous unsuccessful search, in the worst‑case scenario which Wikipedia describes as finding a match for AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA...AAAAAAAAAAAB, it is possible to start from a later place, possibly beyond the B. That runs in n×m time complexity.
The best‑case scenario is that the String sought is a very short prefix of the longer String, in which case it will tend towards constant time. But that isn't going to happen in real life, is it?
 
Greenhorn
Posts: 1
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are multiple resources (including youtube videos) on the internet regarding KMP. You just need to go through one by one till you find something that helps you out. Sometimes a resource that clicks for you may not help others. Anyways from your requirement, I think https://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html should be a good place to start. It is simple enough.
 
dhara das
Greenhorn
Posts: 3
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

xoxulyka mark wrote:There are multiple resources (including youtube videos) on the internet regarding KMP. You just need to go through one by one till you find something that helps you out. Sometimes a resource that clicks for you may not help others. Anyways from your requirement, I think https://www.w3spot.com/2020/07/kmp-algorithm-explained-in-plain-english.html should be a good place to start. It is simple enough.



Thanks.
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic