Longest increasing subsequence
https://en.wikipedia.org/wiki/Longest_increasing_subsequenceProblemSelect some item in array, and keep them ascending.e.g.: 0 8 2 9 3 1 7ans ==> 0 2 3 7 len=4Method1Binary Indexed TreeO(nlogn)ht...
Shuffle & next-permutation
Fisher-Yates shuffle Modern method. https://en.wikipedia.org/wiki/Fisher-Yates_shuffle#Modern_method 易于理解，从最后一个开始loop，在他之前（包括他本身）随便找一个，跟他swap。vector<int> shuffle(vector<int> a) {
fo...
Suffix array 后缀数组
Introduction模版中涉及了若干个变量array ss[] : 待处理的字符串pos : 表示ss[pos]，这个下标，通常指ss[pos->...]这个suffixarray rank[pos] : suffix ss[pos->...] 排第几。array sa[k] or Ith[k] : 排名第k-th的suffix在哪（指的是ss[Ith[k]->...]...
Unrolled linked list 块状链表的一种实现
看了好多文档，依然不得要领。Argument好像这个Unrolled Linked list和块状链表不是一个东西，就暂且认为Unrolled Linked list是一个指导意见好了。。看了几个介绍，有关于maintain操作，只给出了sqrt(n)的理论值，我用了这个方法实现：算两个初始值 BlockSize1=sqrt(n), BlockSize2=1.4*sqrt(n) 这个1.4随...
Aho-Corasick AC自动机
http://www.geeksforgeeks.org/aho-corasick-algorithm-pattern-searching/Part1先来加深一下对Trie的理解：structs TrieNode {
bool flag;
Trie nxt[26];
};(root) --b--> (Node) --u--> (Node) --s-->(No...