圧縮や検索などで応用されているBurrows-Wheeler変換（BW変換）＆逆変換を書いてみました。 （以下の説明では、都合上" "（ホワイトスペース）が最も大きいものとしてソートされていますが、本来" "はもっとも小さい文字です。） 変換は、まず元データとなる…

あんまよくわかんないからといって無視してきたstringstreamクラスが、調べてみるとこれがなかなか使えそうだったので覚書。 strstreamではなくstringstreamの方です。もっといえばヘッダじゃなくてヘッダで読み込む奴の方です。 いったいなんでこんなに警告…

前回の記事 「最長共通部分列(LCS)」 http://d.hatena.ne.jp/g940425/20110210/1297296036 の一般化をしてみました。所謂グローバルアラインメントというやつです。前回のdp[i][j]、つまり「パターン1のi文字目までとパターン2のj文字目までのLCSの長さ」と…

最近更新が滞っている…… なんとかせねば（；ﾟωﾟ）なので少し細かな話題をば。 最長共通部分列問題（LCS）というものは、まあ動的計画法(DP)を学ぶとしたらまず確実に練習問題で出される問題で、「二つの文字列の共通部分列のうち最長のものの長さを求めよ」…