On teh way

KMP in Interview After some questions about basic knowledge of Java, interviewer give Amy the last question: how to find the ‘Longest common substring between two string’ efficiently? Amy thinks for a while and comes up with the DP solution which depends on the core equation of // longest common suffix dp [ i ] [ j ] = m [ i ] == n [ j ] ? dp [ i - 1 ] [ j - 1 ] + 1 : 0 max ( dp [ 1 . . x ] [ 1 . . y ] ) Interviewer check the solution and said, “It’s a good solution. But it’s time complexity is O(n^2) and space complexity is also O(n^2) . Can you come up with better algorithm?” Amy ponder the question again and suddenly the KMP algorithm dawn on her. What is KMP "The KMP algorithm is a very efficient string comparison algorithm which save the time by extra pre-process. When we compare string in common way, we do like this: when a mismatch happens, we reset start point to old_position + 1 : ...xxx...xxy xxy.. ⇑ mismatch ...xxx....

This time, we will solve a common problem – matrix transposition. Description and simple solution Give matrix of n*n , return the transposed matrix. We can come up with the simple solution from the definition of matrix transposition: for x < n for y < x swap( a [x,y], a [y,x]) Different problem It’s so easy, right? Now we move another similar problem: how to efficient transpose a very large matrix(n*n) on the tape? They are similar, both want to transpose a matrix. They are also very different for the data source affect how we can retrieve data effectively. When we have to read data from tape, element can’t be randomly accessed any more. Upper solution works, but too slow. int n = 200 ; // I use LinkedList to simulate the tape LinkedList<Integer> matrix; // init code long start = System.nanoTime(); for ( int i = 0 ; i < n; i++) { for ( int j = i + 1 ; j < n; j++) { final int origin = i * n + j; fin...

KMP wiki introduciton The core thought behind the complex description is avoiding duplicate comparison. For example: aim: ababababd ^ ^ s i pattern: ababd ^ j When aim[i] != pattern[j] , what brute-force solution usually do is set i = s + 1; j = 0 to re-compare it. But actually, we already know aim[s + 1] == pattern[1] && pattern[1] != pattern[0] , so this comparison will always fail. So if there any way to avoid this? kmp algorithm use a pre-processed array – next to handle this. What does next mean Back to upper example, if we using kmp to compare and fail the comparison, i will remain not changed, j = next[j];//2 in this case . aim: ababababd ^ ^ s i pattern: ababd ^ j So what on earth the next is? We try to understand it by example: ------------------------ aim | // // /|y| |/ // // |z|...

It is seems very easy to implement c library function isdigit , but for a library code, performance is very important. So we will try to implement it and make it faster. Function So, first we make it right. int isdigit ( char c) { return c >= '0' && c <= '9' ; } Improvements One – Macro When it comes to performance for c code, macro can always be tried. #define isdigit (c) c >= '0' && c <= '9' Two – Table Upper version use two comparison and one logical operation, but we can do better with more space: # define isdigit(c) table[c] This works and faster, but somewhat wasteful. We need only one bit to represent true or false, but we use a int. So what to do? There are many similar functions like isalpha(), isupper ... in c header file, so we can combine them into one int and get result by table[c]&SOME_BIT , which is what source do. Source code of ctype.h : # define _ISbit(bit) (1 << (...