KMP 算法

KMP算法用于字符串的模式匹配，也就是查找某个字符串里是否存在某个子串，并返回位置，也就是Java/C++里的String.indexOf()方法。  字符串匹配最朴素的算法就是一个一个去比较，出错了就回溯到下一个起点继续比较。这样的复杂度有O(mn)，即原字符串×匹配串。而KMP算法能把时间复杂度降到O(m+n)。KMP这个缩写来自于Knuth，Morris和Pratt，瞬间想到了AVL树。 前面提到，朴素的匹配算法在出错后需要回溯到原来起点。但KMP不需要回溯到起点，直接从出错的位置继续进行比较，从而达到了O(n)。之所以不需要回溯，KMP的秘诀在于其用匹配串(Pattern)计算出来的一个数组F。每当进行字符串的比较卡壳在匹配串的第j个位置时(即Target[i] != Pattern[j])，查阅这个数组F，就可以知道下一次比较时j的值。举个例子： Source串(Target)：              a b a b a b a b a c b 匹配串(Pattern)：                a b a b a c b 根据Pattern得出的数组F:  0 0 0 1 2 3 0  (P怎么计算的后面会讲)  数字代表如果这次mismatch需要回到退几位 一一比较到第五个时前面的字符串都相等，到第六个时，由于Target[5] != Pattern[5]，所以需要知道下一次比较时，新的j值。j值越大，省略的比较越多。对于朴素的匹配算法，一旦卡壳在位置j，则下一次直接把j置0，即从第一个开始比较，并且回到这次比较的起点。而KMP则是得到新的j值（新的j值显然小于当前j值），并且不回到比较的起点，而是从这个地方继续比较下去，不吃回头草。 由于P只需要根据Pattern生成一次，所以KMP特别适用于多个Target字符串，单个Pattern串的情况。 /** * Knuth-Morris-Pratt…

Minimal Number of Coins for Change

Problem: Please implement a function which gets the minimal number of coins, whose value is v1, v2, …, vn, to make change for an amount of money with value t. Any coin with value vi may duplicate for any times to make change. For example, the minimal number of coins to make change for 15…

Maximum Sum of All Sub-arrays

Question: A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n). For example, in the array {1, -2, 3, 10, -4, 7, 2, -5}, its sub-array {3, 10, -4, 7, 2} has the maximum…

The Least k Numbers

Question: Please find out the least k numbers out of n numbers. For example, if given the 8 numbers 4, 5, 1, 6, 2, 7, 3 and 8, please return the least 4 numbers 1, 2, 3 and 4. Analysis: The naïve solution is sort the n input numbers increasingly, and the least k numbers…

Post-order Traversal Sequences of Binary Search Trees

Problem: Determine whether an input array is a post-order traversal sequence of a binary tree or not. If it is, return true; otherwise return false. Assume all numbers in an input array are unique. For example, if the input array is {5, 7, 6, 9, 11, 10, 8}, true should be returned, since it is…

First Character Appearing Only Once

Problem: Implement a function to find the first character in a string which only appears once. For example: It returns ‘b’ when the input is “abaccdeff”. Analysis: Our native solution for this problem may be scanning the input string from its beginning to end. We compare the current scanned character with every one behind it….

Fibonacci Sequences

Recursive (bad performance): class Fibonacci{ public int getFibonacci(int n){ if(n==0) return 0; if(n==1) return 1; return getFibonacci(n-1) + getFibonacci(n-2) } } Iterative ( O(n) ) class Fibonacci{ public int getFibonacci(int n){ int firstNumber = 0; int secondNumber = 1; int total = 0; for(int i = 0; i<=n; i++){ total = firstNumber + secondNumber; firstNumber = secondNumber; secondNumber =…

Reverse a Linked List

algorithm: a temp to store previous node, pointing to that in iterator class ReverseList{ public List reverse(List l){ Node firstNode = l.getFirst(); Node temp = firstNode.next; firstNode.next = null; if(l == null || l.isEmpty) throw new NotValidException(); Node previousNode = firstNode; Node nextNode = temp; while(nextNode != null){ nextNode  =  temp.next; temp.next = previousNode previousNode…

Longest increasing subsequence

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. algorithm: use an array for each element’s longest…

two stack for a queue

points: stack is First In Last Out while queue is First In First Out. stack1 used for push, stack2 used for pop. if we push a, b, c in stack1, when we pop, we push every element into stack2 for pop. when new element comes in, still use stack1 for push. when pop, if stack2…