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


目次

文字列比較(難易度:★★★★☆)

問題

const char* 型の比較元文字列 src と、比較先文字列 dst が与えられたとき、その差分を計算したい。
差分計算にあたっては、下図のような格子状のエディットグラフを考える。

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

エディットグラフにの上辺に比較元文字列、左辺に比較先文字列の各文字を(囲碁のように交点位置に)配置し、 比較元・先の文字が一致する箇所には「\」を配置する。
そして、最左上点から最右下点への最小コスト経路を考える。ただし、各格子点から右または下に移動する場合のコストは1、 各格子点から「\」を通って右下に移動する場合のコストは0とする。
最小コストを与える経路長を「最小編集距離(Shortest Edit Edistance)」と呼ぶ。なぜなら、右の格子点への移動は1文字削除を、 下の格子点への移動は1文字挿入を表すからだ。
また、最小編集距離を与える経路を「最長共通シーケンス(Longest Common Sequence)」と呼ぶ。

例えば、”abc”, “acb” のエディットグラフの各格子点の最小編集距離は下図のようになり、ゴール地点の最小編集距離は2となる。

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

また、上図の最長共通シーケンスは “=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回】

目次 0/1ナップサック問題(難易度:★★★★☆) 0/1ナップサック問題(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主 […]
コメントなし

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

目次 ポーカー:役判定(難易度:★★★☆☆) ポーカー:役判定(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi […]
コメントなし

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

目次 無向グラフ(難易度:★★★☆☆) 無向グラフ(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

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

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第13回~第16回(シーズン4)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで […]
コメントなし

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

目次 文字列比較(難易度:★★★★☆) 文字列比較(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が […]
コメントなし

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

目次 クローズド・ナイト・ツアー(難易度:★★★★☆) クローズド・ナイト・ツアー(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研 […]
コメントなし

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

目次 オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) オセロ:石反転(難易度:★★★☆☆) 両端キュー(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・ […]
コメントなし

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

はじめに 今回から4回にわたって「競技プログラミング風 C++問題集 第9回~第12回(シーズン3)」をお届けする。 各問題は、「問題文」「テストコード」「ヒント」「解答例」「解説」から構成される。 まず、問題を読んで正 […]
コメントなし

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

目次 文字列クラス(難易度:★★★★☆) 文字列クラス(難易度:★★★★☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C+ […]
コメントなし

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

目次 数独(難易度:★★★☆☆) 数独(難易度:★★★☆☆) 関連記事 筆者:津田伸秀 プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中 […]
コメントなし
筆者:津田伸秀
プロフィール:テニス・オセロ・ボードゲーム・パズル類が趣味の年齢不詳のおじさん。 自宅研究員(主席)。vi と C++が好き。迷走中・・・ ボードゲーム・パズル系アプリ開発・リリースしてます。
  • このエントリーをはてなブックマークに追加

PAGE TOP