Spaghetti Sourceの複数パターン検索 (Aho-Corasick)で紹介されているスライドを参考にして、書かれている疑似コードをほぼそのままC++で書き直してみたもの。Trieのvalues_フィールドが保持しているのは、そのノードに到達した時点でマッチしている単語の集…

FloatingMedianとProductOfPricesとUVa 10909で動くのを確認。 template<class T> class BIT{ public: BIT(int n) : n(n), tree(n) {} T read(int idx) { // returns 0 if idx is smaller than 0 T ret = 0; for (; idx >= 0; ret += tree[idx], idx = (idx & (idx + </class>…

どれが最新か分からなくなりそうなのでここにメモ。 // UVA 10989 AC:0.990sec // PKU 3469 AC:5938MS // (時間はdinicの方) class Graph { private: struct Edge { int to, back, flow, cap; Edge(int to, int cap, int back) : to(to), back(back), flow(0…