目次
文字列比較(難易度:★★★★☆)
const char* 型の比較元文字列 src と、比較先文字列 dst が与えられたとき、その差分を計算したい。
差分計算にあたっては、下図のような格子状のエディットグラフを考える。
エディットグラフにの上辺に比較元文字列、左辺に比較先文字列の各文字を(囲碁のように交点位置に)配置し、 比較元・先の文字が一致する箇所には「\」を配置する。
そして、最左上点から最右下点への最小コスト経路を考える。ただし、各格子点から右または下に移動する場合のコストは1、 各格子点から「\」を通って右下に移動する場合のコストは0とする。
最小コストを与える経路長を「最小編集距離(Shortest Edit Edistance)」と呼ぶ。なぜなら、右の格子点への移動は1文字削除を、 下の格子点への移動は1文字挿入を表すからだ。
また、最小編集距離を与える経路を「最長共通シーケンス(Longest Common Sequence)」と呼ぶ。
例えば、”abc”, “acb” のエディットグラフの各格子点の最小編集距離は下図のようになり、ゴール地点の最小編集距離は2となる。
また、上図の最長共通シーケンスは “=a-b=c+b” または “=a+c=b-c” となる。 ただし、「=文字」は文字が等しくエディットグラフ上で右下に進むことを、 「-文字」はsrcの文字を削除すること、すなわちエディットグラフ上では右に進むことを、 「+文字」はdstの文字を挿入すること、すなわちエディットグラフ上では下に進むことを表すものとする。
上記を理解した上で、テストコードの ToDo 部分にコードを記述し、下記のメンバ関数を実装しなさい。
・cchr* 型の引数2つを受け取り、その最小編集距離を返す関数 int SED(cchar* src, cchar* dst)
・cchr* 型の引数2つを受け取り、その最長共通シーケンスを返す関数 string LCS(cchar* src, cchar* dst)
なお、使用するアルゴリズムは、エディットグラフの全格子点の最小編集距離を計算する、単純なものでよいものとする。
#include <iostream> // 標準入出力ライブラリ #include <string> #include <vector> using namespace std; // std 名前空間使用 typedef const char cchar; #define DO_TEST(exp) do_test(exp, __LINE__) void do_test(bool b, int line) { if( b ) return; // OK cout << "\nNG at line " << line << "\n"; exit(1); } class Diff { public: int SED(cchar* src, cchar* dst) { // src, dst の最小編集距離を返す // ToDo: ここにコードを追加し、src, dst の最小編集距離を返す return 0; } string LCS(cchar* src, cchar* dst) { // src, dst の最長共通シーケンスを返す // ToDo: ここにコードを追加し、src, dst の最長共通シーケンスを返す return ""; } private: int m_M; // src 文字列長 int m_M1; // m_M + 1 int m_N; // dst 文字列長 int m_N1; // m_N + 1 vector<int> m_v; // 各格子点の最小編集距離1次元配列 }; int main() { Diff d; DO_TEST( d.SED("", "") == 0 ); DO_TEST( d.SED("abc", "abc") == 0 ); DO_TEST( d.SED("abc", "ac") == 1 ); // 削除1 DO_TEST( d.SED("abc", "abXc") == 1 ); // 挿入1 DO_TEST( d.SED("abc", "acb") == 2 ); // 削除1, 挿入1 DO_TEST( d.SED("abc", "XYZZZ") == 8 ); // 削除3、挿入5 DO_TEST( d.SED("abcd", "ad") == 2 ); // 削除2 // DO_TEST( d.LCS("", "") == "" ); DO_TEST( d.LCS("abc", "abc") == "=a=b=c" ); DO_TEST( d.LCS("abc", "ac") == "=a-b=c" ); // 1文字削除 DO_TEST( d.LCS("abc", "abXc") == "=a=b+X=c" ); // 1文字挿入 // cout << "\nGood Job!\n"; return 0; }
関連記事

競技プログラミング風 C++問題集【第16回】

競技プログラミング風 C++問題集【第15回】

競技プログラミング風 C++問題集【第14回】

競技プログラミング風 C++問題集【第13回】

競技プログラミング風 C++問題集【第12回】

競技プログラミング風 C++問題集【第11回】

競技プログラミング風 C++問題集【第10回】

競技プログラミング風 C++問題集【第9回】

競技プログラミング風 C++問題集【第8回】

競技プログラミング風 C++問題集【第7回】
![]() |
筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。 |