任意のコンテナに対してdiffをとれるようにテンプレートにしました。 ポイントはテンプレートになっているのが、diffの入り口Diff::ond関数だけというところです。このためdiffを求めるプログラムの大半をバイナリとしてライブラリ化することもできます。ま…

経路を記憶するしくみを追加し、実際に文字列を比較してみます。 コードの様子が変わったように見えるかもしれませんが、やっていることの実質はおなじです。 メンバのtree_に編集の操作(delete/common/add)がツリーとして記録されます。diffの最後で見つか…

「O(ND)」というのは、この手続きにかかる計算量のことですが、それがそのままアルゴリズムのことをさす言葉になっているようです。 詳しい解説はこのページなどをみてもらうとして、ともかく実装。 #include <string> #include <vector> #include <stdexcept> int snake(int x, int y, </stdexcept></vector></string>…

diffをつくる(2)で掲載したコードは文字列を比較するコードですが、std::stringを他のコンテナに替えればそのコンテナどうしのdiffがとれます。 任意のコンテナのdiffをとれるようにテンプレートにしたものを掲載。この例ではstd::stringのdiffとstd::vector…

昨日のコードでつくったグラフをもとに、SES(Shortest Edit Script)を見つけるコードを追加しました。体裁が変わったように見えますが、makeGraphまでは基本的に昨日と同じコードです。 今日のキモはfindSESのコード。もっとも少ない手順で一方の文字列から…

わけあって、diffを自作中。で、いろいろネット上で情報を集めている最中。 検索をかけてみるとこのページがあちこちからリンクされていたので、読んでいるんですが…後半部分がまだよくわかりません。 仕方がないので、理解したところまでコードに変換してい…

タイトルがよくないと思う。前著にあやかってタイトルが決められたんだと思うんですが、内容とあってないような気がします。個人的な話ですがそのタイトルから敬遠していた部分があります。最近になって著者のブログなどを拝見するうちに興味がわいて読んで…

バージョン管理には久しくSubversionを使っていて、その後分散バージョン管理が便利そうだとMercurialを使いはじめました。 さらにその後、Gitもわりと使われていることを知り、少なくとも使えるようにしておこうと一通り使い方を調べてみたんですが…git-pus…

以前、部屋の片付けをしたときにどこかの箱に放り込んでそのまま行方不明になっていた「数学ガール」を、今日ようやく発掘しました。これでコミックス上巻を読んでから気になっていた気になっていたことが解消。 なにが気になっていたかというと、ミルカさん…

無気力の心理学―やりがいの条件 (中公新書 (599))作者: 波多野誼余夫,稲垣佳世子出版社/メーカー: 中央公論新社発売日: 1981/01/22メディア: 新書購入: 3人 クリック: 52回この商品を含むブログ (35件) を見る 最近読んだ本。 効力感というのは、おおざっぱ…

ちょっと古いニュースですが、先ほど初めて目にしたので。 ケータイ「契約」実績で「特別採用」 学生から不満と批判の声 : J-CASTニュース 最初、リンクされていたブログの記事などで概要を目にしたときは「そんな乱暴な話があるのか」と思ったんですが、今…