Knuth–Morris–Pratt(KMP) Pattern Matching(Substring search)
Why Stack Overflow recommends it
Stack Overflow users link it as an intuitive reference for KMP when answering questions about substring search, repeated patterns and matching one array inside another.
Recommended by 3 people across 3 different months, 2017 to 2018.
What it is
A 12-minute walkthrough of the Knuth-Morris-Pratt substring search algorithm by Tushar Roy. It explains how the prefix/suffix lookup table is built and how it lets the search skip redundant comparisons, with the Java code linked in the description.
What people said
Recommends skrubber · 2017-10 · Stack Overflow · on “Getting indices of patterns found in a sequence using KNUTH-MORRIS-PRATT?”
This implementation of KMP is not efficient though. You can choose functional programming though. A good intuitive reference is here: [this video]
Recommends thebenman · 2017-11 · Stack Overflow · on “Find out recursive pattern in a string java”
This can also be solved using a part of the Knuth–Morris–Pratt Algorithm [LINK] . The idea is to build a 1-D array with each entry representing a character in the word. For each character i in the word we check if there is a prefix which is also a suffix in the word up 0 to i . The reason being if we have common suffix and prefix we can continue searching from the character after prefix ends which we update the array with the corresponding character index. For s="abcababcababcab" , the array will be Index : 0 1 2 3 4 5 6 7 8 String: a b c a b c a b c KMP : 0 0 0 1 2 3 4 5 6 For Index = 2 , we see that there is no suffix which is also the prefix in the string ab i.e) up until Index = 2 For In
Recommends bitbyter · 2018-05 · Stack Overflow · on “Determining if one array is contained in another”
This is same as searching a substring in a string. There we are comparing characters, here we will compare numbers or array elements. KMP 1 [this video] algorithm is sought for such questions.