today just decided to write the Knuth–Morris–Pratt string searching algorithm , implementation in ruby. As you can see that the algorithm is divided into two parts , one is the preprocess , which is the crux of the Algo and the actual string searching using the preprocessed metadata. The preprocess function is run only on the patterns, and it calculates π[i] = the longest proper prefix of pattern[0..i] , which is also a suffix of pattern[0..i]. e.g. if the pattern you are searching for is P = [ ‘A’,'B’,'A’,'B’,'A’,'C’,'A’] the π array will look like π = [ 0,0,1,2,3,0,1] which shows that longest running prefix of the pattern is ABA . Buy doing the above calculations the algo saves itself some of the comparisons which it had to do in the naive , brute force approach. if you get the preprocessing function then the rest of the things are straight forward , the algorithm is intelligent enough to understand that if next char in the seq does...