レーベンシュタイン距離を完全に理解した！(C++編)
※この記事はQiitaからの移行記事です こんにちは、競プロ絶賛勉強中のyapattaです。 AOJ(AIZU ONLINE JUDGE)のレーベンシュタイン距離の問題を解くことができなかったから、理解するために記事を書いた。プログラミングをやってない人でも理解できる記事を書きたい。 この記事を見て、レーベンシュタイン距離について理解して頂ければ幸いである。 最後に実装されたコードが書かれているので、コードだけみたい人は是非最後だけ見て欲しい。 1)レーベンシュタイン距離(編集距離)とは？ レーベンシュタイン距離とは、とりあえず２つの文字列がどのぐらい違っている文字列か表す指標であると理解してもらえるといい。 文字列Aの中の1文字を、置換、挿入、削除を繰り返しすことで、一方の文字列Aをもう一方の文字列Bに変形する。この繰り返しの最小回数をレーベンシュタイン距離という。詳しくは以下↓ レーベ
部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集 - Qiita
特に名前のついていないテクニックが、名前がつくことで広く知れ渡って「典型」と化すことはよくあることと思います。競プロ界で俗に言う imos 法などはその代表例と言えます。桁 DP もその呼び名が固有名詞化したことで、smaller フラグを用いる考え方が普及したイメージです。 これに対して「部分文字列を走査する DP」のような名前のついていないテクニックは、なかなか典型と受け止められないイメージがあります。AUPC 2018 day3 北大セットの最終問題の解法も、この DP の考え方を知っていれば自然なものに思えます。本記事ではこの「部分列 DP」を特集してみます。誰かがいい名前を付けて固有名詞化してくれたらいいなと思いつつ... 0. はじめに --- 部分文字列とは 文字列 $S$ (例えば "nyanpasu") に対して、 $S$ を構成する文字を $0$ 文字以上取り除き 残っ
HTTPパーサにおけるSSE4.2最適化の威力と注意点 - Cybozu Inside Out | サイボウズエンジニアのブログ
こんにちは、サイボウズ・ラボの光成です。 PicoHTTPParserは@kazuhoさんたちが開発している高速なHTTPパーサです。 同じ作者によるHTTPサーバH2Oにも使われています。 11月4日の開発ブログによると、その時点でNode.jsなどに使われているhttp-parserの10倍程度の速度を誇るそうです（現在はhttp-parserも速度向上しその差は縮まりました。それでも4倍以上の差があるようです）。 該当ブログにはその高速化のためのノウハウが書かれていて大変興味深いです。ただIntel系CPUに搭載されているSIMD命令は用いられていませんでした。今回、@kazuhoさんと一緒に文字列処理専用のSSE4.2を用いることで1.7～1.9倍の高速化を達成しました（Improving Parser Performance using SSE Instructions (in
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Welcome adilet.org - BlueHost.com
