Linear-time pattern matching. Z-values and Z-algorithm
Why Code Review Stack Exchange recommends it
Code Review Stack Exchange commenters point people to it when they need to understand the Z-algorithm for string matching and similarity problems.
Recommended by 2 people across 2 different months, 2012 to 2014.
What it is
A 52-minute UC Davis lecture (Lecture 21) covering Dan Gusfield's approach to linear-time exact pattern matching, built on Z-values and the Z-algorithm. It is a university algorithms-on-strings lecture.
What people said
Strong rec Sergey Makarenko · 2012-01 · Code Review Stack Exchange · on “Optimizing string match algorithm”
Actually for this problem you could use simpler algorithm related to string pattern matching. There is an excellent video by Dan Gasfield Linear-time pattern matching. Z-values and Z-algorithm [this video] . Or you could read the first chapter of his book Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology [LINK] which will be helpful for some other problems from InterviewStreet.
Recommends Shiv · 2013-09 · Code Review Stack Exchange · on “Hackers Ranking String Similarity”
Try studying z-algorithm. This question is a very very simple modification of the z-array you get as part of the z-algorithm. See this for the tutorial or youtube video tutorials
Cites SohamC · 2014-06 · Code Review Stack Exchange · on “Z-Algorithm for pattern matching in strings”
I was trying to refactor the following Python code (keeping the same time-complexity) which is an implementation of Z-Algorithm for pattern matching in strings. def compute_z(string): n = len(string) z = [n] L = R = 0 for i in xrange(1,n): if (i > R): L = R = i while (R < n and string[R-L] == string[R]): R+=1 z.append(R-L) R -= 1 else: k = i-L if (z[k] < R-i): z.append(z[k]) else: L = i while (R < n and string[R-L] == string[R]): R += 1 z.append(R-L) R -= 1 I was thinking of using lambda but it returns expressions and I need to store the values in z array. So I could not think of a way of using lambda . The max I could refactor was this: def g(L,R,string): L=i while (R < len(string) and stri