Pages in Algorithm

Algorithm Question Substring Search KMP

Question LeetCode has this question Implement strStr(). Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. Tags: Two Pointers, String. Let’s denote haystack length N, needle length M, character table size R (256 for extended ASCII). Java’s String class method indexOf() uses brute force algorithm O(MN). Examples: haystacsflksdjflkshhaystackneeneeneedle needle naslkfjskjlhhhh needle Method 1 2D DFA KMP Knuth Morris Pratt O(N) time complexity.

---

Sorting Algorithm Summary

The following table summarizes common characteristics of popular sorting algorithms, not including string sort algorithms (I may add those later here or write another separate post). algorithm In Place? Stable? parallel? worst average best remarks selection y n n N2/2 N2/2 N2/2 N exchanges insertion y y n N2/2 N2/4 N use for small N or partially ordered shell y n n ?

---