Searching for Patterns | Set 2 (KMP Algorithm) - GeeksforGeeks


Searching for Patterns | Set 2 (KMP Algorithm) - GeeksforGeeks
Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

The KMP matching algorithm uses degenerating property (pattern having same sub-patterns appearing more than once in the pattern) of the pattern and improves the worst case complexity to O(n). The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of next window. We take advantage of this information to avoid matching the characters that we know will anyway match. 
Matching Overview
txt = "AAAAABAAABA" 
pat = "AAAA"

We compare first window of txt with pat
txt = "AAAAABAAABA" 
pat = "AAAA"  [Initial position]
We find a match. This is same as Naive String Matching.

In the next step, we compare next window of txt with pat.
txt = "AAAAABAAABA" 
pat =  "AAAA" [Pattern shifted one position]
This is where KMP does optimization over Naive. In this 
second window, we only compare fourth A of pattern
with fourth character of current window of text to decide 
whether current window matches or not. Since we know 
first three characters will anyway match, we skipped 
matching first three characters. 

Need of Preprocessing?
An important question arises from above explanation, 
how to know how many characters to be skipped. To know 
this, we pre-process pattern and prepare an integer array 
lps[] that tells us count of characters to be skipped. 
  • For each sub-pattern pat[0..i] where i = 0 to m-1, lps[i] stores length of the maximum matching proper prefix which is also a suffix of the sub-pattern pat[0..i].
       lps[i] = the longest proper prefix of pat[0..i] 
                  which is also a suffix of pat[0..i]. 
    Unlike Naive algorithm, where we slide the pattern by one and compare all characters at each shift, we use a value from lps[] to decide the next characters to be matched. The idea is to not match character that we know will anyway match.
    How to use lps[] to decide next positions (or to know number of characters to be skipped)?
    • We start comparison of pat[j] with j = 0 with characters of current window of text.
    • We keep matching characters txt[i] and pat[j] and keep incrementing i and j while pat[j] and txt[i] keep matching.
    • When we see a mismatch
      • We know that characters pat[0..j-1] match with txt[i-j+1…i-1] (Note that j starts with 0 and increment it only when there is a match).
      • We also know (from above definition) that lps[j-1] is count of characters of pat[0…j-1] that are both proper prefix and suffix.
      • From above two points, we can conclude that we do not need to match these lps[j-1] characters with txt[i-j…i-1] because we know that these characters will anyway match.
Preprocessing Algorithm:
In the preprocessing part, we calculate values in lps[]. To do that, we keep track of the length of the longest prefix suffix value (we use len variable for this purpose) for the previous index. We initialize lps[0] and len as 0. If pat[len] and pat[i] match, we increment len by 1 and assign the incremented value to lps[i]. If pat[i] and pat[len] do not match and len is not 0, we update len to lps[len-1].
    pat[] = "AAACAAAA"
    
    len = 0, i  = 0.
    lps[0] is always 0, we move 
    to i = 1
    
    len = 0, i  = 1.
    Since pat[len] and pat[i] match, do len++, 
    store it in lps[i] and do i++.
    len = 1, lps[1] = 1, i = 2
    
    len = 1, i  = 2.
    Since pat[len] and pat[i] match, do len++, 
    store it in lps[i] and do i++.
    len = 2, lps[2] = 2, i = 3
    
    len = 2, i  = 3.
    Since pat[len] and pat[i] do not match, and len > 0, 
    set len = lps[len-1] = lps[1] = 1
    
    len = 1, i  = 3.
    Since pat[len] and pat[i] do not match and len > 0, 
    len = lps[len-1] = lps[0] = 0
    
    len = 0, i  = 3.
    Since pat[len] and pat[i] do not match and len = 0, 
    Set lps[3] = 0 and i = 4.
    
    len = 0, i  = 4.
    Since pat[len] and pat[i] match, do len++, 
    store it in lps[i] and do i++.
    len = 1, lps[4] = 1, i = 5
    
    len = 1, i  = 5.
    Since pat[len] and pat[i] match, do len++, 
    store it in lps[i] and do i++.
    len = 2, lps[5] = 2, i = 6
    
    len = 2, i  = 6.
    Since pat[len] and pat[i] match, do len++, 
    store it in lps[i] and do i++.
    len = 3, lps[6] = 3, i = 7
    
    len = 3, i  = 7.
    Since pat[len] and pat[i] do not match and len > 0,
    set len = lps[len-1] = lps[2] = 2
    
    len = 2, i  = 7.
    Since pat[len] and pat[i] match, do len++, 
    store it in lps[i] and do i++.
    len = 3, lps[7] = 3, i = 8
    
    We stop here as we have constructed the whole lps[].
    void KMPSearch(String pat, String txt)
    {
        int M = pat.length();
        int N = txt.length();
 
        // create lps[] that will hold the longest
        // prefix suffix values for pattern
        int lps[] = new int[M];
        int j = 0// index for pat[]
 
        // Preprocess the pattern (calculate lps[]
        // array)
        computeLPSArray(pat,M,lps);
 
        int i = 0// index for txt[]
        while (i < N)
        {
            if (pat.charAt(j) == txt.charAt(i))
            {
                j++;
                i++;
            }
            if (j == M)
            {
                System.out.println("Found pattern "+
                              "at index " + (i-j));
                j = lps[j-1];
            }
 
            // mismatch after j matches
            else if (i < N && pat.charAt(j) != txt.charAt(i))
            {
                // Do not match lps[0..lps[j-1]] characters,
                // they will match anyway
                if (j != 0)
                    j = lps[j-1];
                else
                    i = i+1;
            }
        }
    }
 
    void computeLPSArray(String pat, int M, int lps[])
    {
        // length of the previous longest prefix suffix
        int len = 0;
        int i = 1;
        lps[0] = 0// lps[0] is always 0
 
        // the loop calculates lps[i] for i = 1 to M-1
        while (i < M)
        {
            if (pat.charAt(i) == pat.charAt(len))
            {
                len++;
                lps[i] = len;
                i++;
            }
            else  // (pat[i] != pat[len])
            {
                // This is tricky. Consider the example.
                // AAACAAAA and i = 7. The idea is similar
                // to search step.
                if (len != 0)
                {
                    len = lps[len-1];
 
                    // Also, note that we do not increment
                    // i here
                }
                else  // if (len == 0)
                {
                    lps[i] = len;
                    i++;
                }
            }
        }
    }
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm
It never re-compares a text symbol that has matched a pattern symbol.
  Definition:  Let A be an alphabet and  x = x0 ... xk-1,  k element natural numbers   a string of length k over A.
A prefix u of x or a suffix u of x is called a proper prefix or suffix, respectively, if unot equalx, i.e. if its length b is less than k.
border of x is a substring r with
r  =  x0 ... xb-1  and  r  =  xk-b ... xk-1   where  b element {0, ..., k-1}
A border of x is a substring that is both proper prefix and proper suffix of x. We call its length b the width of the border.
Example:  
0123456789...
abcabcabd
abcabd
abcabd
The symbols at positions 0, ..., 4 have matched. Comparison c-d at position 5 yields a mismatch. The pattern can be shifted by 3 positions, and comparisons are resumed at position 5.
The shift distance is determined by the widest border of the matching prefix of p. In this example, the matching prefix is abcab, its length is j = 5. Its widest border is ab of width b = 2. The shift distance is j – b  =  5 – 2  =  3.
In the preprocessing phase, the width of the widest border of each prefix of the pattern is determined. Then in the search phase, the shift distance can be computed according to the prefix that has matched.

Theorem:  Let rs be borders of a string x, where |r| < |s|. Then r is a border of s.
Proof:  Figure 1 shows a string x with borders r and s. Since r is a prefix of x, it is also a proper prefix of s, because it is shorter than s. But r is also a suffix of x and, therefore, proper suffix of s. Thus r is a border of s.
Borders r, s of a string x
Figure 1:  Borders r, s of a string x
If s is the widest border of x, the next-widest border r of x is obtained as the widest border of s etc.

Definition:  Let x be a string and a element A a symbol. A border r of x can be extended by a, if ra is a border of xa.
Extension of a border
Figure 2:  Extension of a border
Figure 2 shows that a border r of width j of x can be extended by a, if xj = a.

In the preprocessing phase an array b of length m+1 is computed. Each entry b[i] contains the width of the widest border of the prefix of length i of the pattern (i = 0, ..., m). Since the prefix ε of length i = 0 has no border, we set b[0] = -1.
Prefix of length i of the pattern with border of width b[i]
Figure 3:  Prefix of length i of the pattern with border of width b[i]
Provided that the values b[0], ..., b[i] are already known, the value of b[i+1] is computed by checking if a border of the prefix p0 ...pi-1 can be extended by symbol pi. This is the case if pb[i] = pi (Figure 3). The borders to be examined are obtained in decreasing order from the values b[i], b[b[i]] etc.
The preprocessing algorithm comprises a loop with a variable j taking these values. A border of width j can be extended by pi, ifpj = pi. If not, the next-widest border is examined by setting j = b[j]. The loop terminates at the latest if no border can be extended (j = -1).
After increasing j by the statement j++ in each case j is the width of the widest border of p0 ... pi. This value is written to b[i+1] (tob[i] after increasing i by the statement i++).

Preprocessing algorithm
void kmpPreprocess()
{
    int i=0, j=-1;
    b[i]=j;
    while (i<m)
    {
        while (j>=0 && p[i]!=p[j]) j=b[j];
        i++; j++;
        b[i]=j;
    }
}
Example:  For pattern p = ababaa the widths of the borders in array b have the following values. For instance we have b[5] = 3, since the prefix ababa of length 5 has a border of width 3.
j:0123456
p[j]:ababaa
b[j]:-1001231
Searching algorithm
void kmpSearch()
{
    int i=0, j=0;
    while (i<n)
    {
        while (j>=0 && t[i]!=p[j]) j=b[j];
        i++; j++;
        if (j==m)
        {
            report(i-j);
            j=b[j];
        }
    }
}
When in the inner while loop a mismatch at position j occurs, the widest border of the matching prefix of length j of the pattern is considered (Figure 5). Resuming comparisons at position b[j], the width of the border, yields a shift of the pattern such that the border matches. If again a mismatch occurs, the next-widest border is considered, and so on, until there is no border left (j = -1) or the next symbol matches. Then we have a new matching prefix of the pattern and continue with the outer while loop.
0123456789...
ababbabaa
ababac
ababac
ababac
ababac
ababac

http://jakeboxer.com/blog/2009/12/13/the-knuth-morris-pratt-algorithm-in-my-own-words/
Here’s the partial match table for the pattern “abababca”:
1
2
3
char:  | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
Proper prefix: All the characters in a string, with one or more cut off the end. “S”, “Sn”, “Sna”, and “Snap” are all the proper prefixes of “Snape”.
Proper suffix: All the characters in a string, with one or more cut off the beginning. “agrid”, “grid”, “rid”, “id”, and “d” are all proper suffixes of “Hagrid”.
With this in mind, I can now give the one-sentence meaning of the values in the partial match table:
The length of the longest proper prefix in the (sub)pattern that matches a proper suffix in the same (sub)pattern.
How to use the Partial Match Table

1
2
3
char:  | a | b | a | b | a | b | c | a |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |

The first time we get a partial match is here:

1
2
3
bacbababaabcbab
 |
 abababca

This is a partial_match_length of 1. The value at table[partial_match_length - 1] (or table[0]) is 0, so we don’t get to skip ahead any. 
The next partial match we get is here:

1
2
3
bacbababaabcbab
    |||||
    abababca

This is a partial_match_length of 5. The value at table[partial_match_length - 1] (or table[4]) is 3. That means we get to skip ahead partial_match_length - table[partial_match_length - 1] (or 5 - table[4] or 5 - 3or 2) characters:

1
2
3
4
5
// x denotes a skip

bacbababaabcbab
    xx|||
      abababca
http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/stringmatchingclasses/KmpStringMatcher.java
http://tekmarathon.com/2013/05/14/algorithm-to-find-substring-in-a-string-kmp-algorithm/

p    :  a   b   c   a   b   d   a   b   c
p[i] :  0   1   2   3   4   5   6   7   8
b[i] : -1   0   0   0   1   2   0   1   2   3
b[0] is computed by looking at longest prefix and suffix match of the substring of p[0…0-1] as p[-1] is not defined, hence b[0] is given -1
b[1] is computed by looking at longest prefix and suffix match of the substring of p[0…1-1] = b[0] = A, since there wont be any prefix and suffix for one letter word, b[1] is 0.
Note: For any given pattern b[0] and b[1] are always fixed

    public int[] preProcessPattern(char[] ptrn) {
        int i = 0, j = -1;
        int ptrnLen = ptrn.length;
        int[] b = new int[ptrnLen + 1];
        b[i] = j;
        while (i < ptrnLen) {
            while (j >= 0 && ptrn[i] != ptrn[j]) {
                // if there is mismatch consider next widest border
                j = b[j];
            }
            i++;
            j++;
            b[i] = j;
        }
        return b;
    }  
    public void searchSubString(char[] text, char[] ptrn) {
        int i = 0, j = 0;
        // pattern and text lengths
        int ptrnLen = ptrn.length;
        int txtLen = text.length;
        // initialize new array and preprocess the pattern
        int[] b = preProcessPattern(ptrn);
        while (i < txtLen) {
            while (j >= 0 && text[i] != ptrn[j]) {
                System.out.println("Mismatch happened, between text char "
                        + text[i] + " and pattern char " + ptrn[j]
                        + ", \nhence jumping the value of " + "j from " + j
                        + " to " + b[j] + " at text index i at " + i
                        + " based on partial match table");
                j = b[j];
            }
            i++;
            j++;
            // a match is found
            if (j == ptrnLen) {
                System.out.println("FOUND SUBSTRING AT i " + i + " and index:"
                        + (i - ptrnLen));
                System.out.println("Setting j from " + j + " to " + b[j]);
                j = b[j];
            }
        }
    }
https://weblogs.java.net/blog/potty/archive/2012/05/10/string-searching-algorithms-part-ii
Also check http://algs4.cs.princeton.edu/53substring/KMP.java.html
http://algs4.cs.princeton.edu/53substring/KMPplus.java.html
http://www.sanfoundry.com/java-program-knuth-morris-pratt-algorithm/

https://gist.github.com/shonenada/4266864

static int[] getNext(String p){ int i=1,j=0;
int[] next = new int[p.length()+2];
char[] pattern = p.toCharArray();
next[0] = -1;
next[1] = 0;
while(i<p.length()-1){
if(pattern[i] == pattern[j]){
i++;
j++;
next[i] = next[j];
}
else if(j == 0){
next[i+1] = 0;
i++;
}
else{
j = next[j];
}
}
return next;
}
static int findKMPSub(String str, String p,int start, int next[]){
char[] string = str.toCharArray();
char[] pattern = p.toCharArray();
int i = start;
int j=0,v;
while(i<str.length() && j<p.length()){
if(j == -1 || string[i] == pattern[j]){
i++;
j++;
}
else{
j = next[j];
}
}
if ( j == p.length()){
v = i - p.length();
}else{
v = -1;
}
return v;
}
https://gist.github.com/shoenig/1430733/250b4184dc4a2dd31aa136e2fbdded5f90489a64

public static Integer[] createTable(char[] W) {
Integer[] table = new Integer[W.length];
int pos = 2; // cur pos to compute in T
int cnd = 0; // index of W of next character of cur candidate substr
// first few values are fixed
table[0] = -1; // table[0] := -1
table[1] = 0; // table[1] := 0
while(pos < W.length) {
// first case: substring is still good
if(W[pos-1] == W[cnd]) {
table[pos] = cnd;
cnd += 1;
pos += 1;
} else if(cnd > 0)
cnd = table[cnd];
else {
table[pos] = 0;
pos += 1;
}
}
return table;
}
// S := text string
// W := word
public static int kmp(char[] S, char[] W) {
if(W.length == 0) // substr is empty string
return 0;
if(S.length == 0) // text is empty, can't be found
return -1;
int m = 0; // index of beg. of current match in S
int i = 0; // pos. of cur char in W
Integer[] T = createTable(S);
while(m+i < S.length) {
if(W[i] == S[m+i]) {
if(i == W.length-1)
return m;
i += 1;
} else {
m = (m+i - T[i]);
if(T[i] > -1)
i = T[i];
else
i = 0;
}
}
return -1;
}

X. Pat[0]=0;
https://www.fmi.uni-sofia.bg/fmi/logic/vboutchkova/sources/KMPMatch_java.html

void KMPSearch(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);
    // create lps[] that will hold the longest prefix suffix values for pattern
    int *lps = (int *)malloc(sizeof(int)*M);
    int j  = 0;  // index for pat[]
    // Preprocess the pattern (calculate lps[] array)
    computeLPSArray(pat, M, lps);
    int i = 0;  // index for txt[]
    while (i < N)
    {
      if (pat[j] == txt[i])
      {
        j++;
        i++;
      }
      if (j == M)
      {
        printf("Found pattern at index %d \n", i-j);
        j = lps[j-1];
      }
      // mismatch after j matches
      else if (i < N && pat[j] != txt[i])
      {
        // Do not match lps[0..lps[j-1]] characters,
        // they will match anyway
        if (j != 0)
         j = lps[j-1];
        else
         i = i+1;
      }
    }
    free(lps); // to avoid memory leak
}
void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // lenght of the previous longest prefix suffix
    int i;
    lps[0] = 0; // lps[0] is always 0
    i = 1;
    // the loop calculates lps[i] for i = 1 to M-1
    while (i < M)
    {
       if (pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if (len != 0)
         {
           // This is tricky. Consider the example AAACAAAA and i = 7.
           len = lps[len-1];
           // Also, note that we do not increment i here
         }
         else // if (len == 0)
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}

https://dzone.com/articles/algorithm-week-morris-pratt
Read full article from Searching for Patterns | Set 2 (KMP Algorithm) - GeeksforGeeks

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts