Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
Spaghetti Source - 複数パターン検索 (Aho-Corasick)
説明 複数のパターン文字列からなる集合と長い文字列が与えられる．長い文字列に対してマッチするパターン文字列をすべて求めるアルゴリズムが Aho Corasick である．これは複数パターン文字列をあらかじめ trie に変換してから KMP を実行し，パターンマッチング・オートマトンを構成していることになる． 詳しくは適当な成書や http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf などを参考のこと． 計算量 構築 O(m)． 検索 O(n + m)． ただし m はパターンの文字列長の総和，n は検索テキスト長． 使い方 struct PMA; を適宜設定のこと． buildPMA(char *p[], int m) 0 ... m-1 の複数の検索パターンから，パターンマッチング・オートマトンを構築する． match(c
Spaghetti Source - Trie
説明 Trie は文字列のための多分探索木である．各頂点はアルファベットで指定できる枝の集合を持つ．文字列ひとつが根からアルファベットで辺を手繰ることで行き着く頂点に対応する． アルファベットサイズを定数と見たとき，文字列の数に対して trie のサイズは O(m) である．ただし m は蓄えられている文字列の長さの総和．これは通常の二分木で蓄えるのに対して特に不利ではない．検索性能は検索文字列の長さ n に対して O(n) である．これはうまく実装された二分木が O(n + log m) であることと比較して高速である． 結論として，文字列に対して std::map を使いたい場合は trie で代用できないか考えるべきである． 計算量 検索: O(n)，ただし n は検索する文字列長． 使い方 Trie *find(char *t, Trie *v); t に対応する Trie の頂点
Spaghetti Source - std::string の基本操作
ソースコード vector<string> splitAll(string s, string t) { vector<string> v; for (int p = 0; (p = s.find(t)) != s.npos; ) { v.push_back(s.substr(0, p)); s = s.substr(p + t.size()); } v.push_back(s); return v; } vector<string> split(string s, string t) { vector<string> v; int p = s.find(t); if (p != s.npos) { v.push_back(s.substr(0, p)); s = s.substr(p + t.size()); } v.push_back(s); return v; } string re
Spaghetti Source - 各種アルゴリズムの C++ による実装
ACM/ICPC（プログラミングコンテスト）系列の問題を解くことを目標にして，各種アルゴリズムを C++ で実装してみた．極めて意地が悪い類の問題には対応していないし，特定の入力に対して高速に動くということもない．計算量も最良とは限らない． これらを参考にする方への注意とお願い： これらの記述は正確とは限りません．参考文献を参照することを強く推奨します．間違っている場合は是非教えてください． これらのプログラムは間違っているかもしれません．各人で検証することを強く推奨します．バグがあれば是非教えてください． 分類が怪しいので，これはこっちだろう，ということがあればコメントを下さると助かります． 注意！ 現在書き換え中 TODO 分類を正しく行う． 全体的に説明と使い方を詳しく． Verify していないものを Verify． ボロノイ図（いつになることやら……） 基本 テンプレート グラフ
Spaghetti Source - アトキンのふるい
ソースコード void sieve_of_atkin() { int n; for (int z = 1; z <= 5; z += 4) { for (int y = z; y <= sqrtN; y += 6) { for (int x = 1; x <= sqrtN && (n = 4*x*x+y*y) <= N; ++x) isprime[n] = !isprime[n]; for (int x = y+1; x <= sqrtN && (n = 3*x*x-y*y) <= N; x += 2) isprime[n] = !isprime[n]; } } for (int z = 2; z <= 4; z += 2) { for (int y = z; y <= sqrtN; y += 6) { for (int x = 1; x <= sqrtN && (n = 3*x*x+y*
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
