Categories

8

Total

Reservoir Sampling

We would like to select k items from a data stream of unkown size n and all the items in the stream should be equally likely to be choosen. However, there is no sufficient memory to save......

Z algorithm - string searching

Assume that we have a string s of length n. Z algorithm runs in linear time O(n) to calculate the lengths of the longest substringd starting from s[i] (i=0, 1...n-1) which is also a prefix of s[0..n-1......