読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 526 : String Distance and Transform Process

UVa 動的計画法 編集距離 経路復元

問題リンク;String Distance and Transform Process

問題概要:
2つの文字列が与えられる
最初の文字列に以下の3つの動作だけを使用して目的の文字列に変更するためにかかる
動作の最小の使用回数とその動作を出力せよ
1:文字列の任意の場所にアルファベットを追加する
2:文字列の任意の場所のアルファベットを削除する
3:文字列の任意の場所のアルファベットを任意のアルファベットに置換する

解法;
動的計画法で解いた
よくある編集距離の問題の経路復元
2つの文字列をA,Bとし、Aが初期の文字列、Bが目的の文字列とする
dp[Aの長さ+1][Bの長さ+1] という配列を用意する
配列のインデックスが文字列のインデックスに対応する
ただし、文字列は1-indexedとし、0は空白文字とする
dp[i][j] := 文字列iから文字列jにするまでにかかる最小の動作を使用した回数  とする
dp[i][0] = i //A[1..i]までを空文字("")にするためにかかる最小の動作回数
dp[0][i] = i //空文字("")からB[1..i]にするためにかかる最小の動作回数
とする
dp配列は次の様に更新する

dp[i][j] = min(dp[i][j-1]+1, //追加, 文字列B[1..j-1]までが完成しているのでそこにB[j]を追加しB[1..j]を作る
                     dp[j-1][i]+1,//削除、文字列B[1..j]+A[i]という形になっているのでA[i]を削除しB[1..j]とする
                     dp[i-1][j-1]+!(A[i]==B[j]))//置換、文字列B[1..j-1]+A[i]という形になっている、もしA[i] == B[j]ならなにもしない(既にB[1..j]となっている)が、A[i] != B[j]ならA[i]をB[j]に置換してB[1..j]とする

この問題では、経路を復元しなければいけないためpath[y][x]という配列も用意し、
dp配列と一緒に更新する

復元する際には、文字列のどのインデックスに何をしたかを出力しないといけない
xとy座標をもって再帰を利用して復元していく
Insertする時、文字列はB[1..x-1]となっているためInsertする場所のインデックスはxとなる
Deleteする時、文字列はB[1..x]+A[x]となっているため、Deleteする場所のインデックスはx+1
Replaceする時、文字列はB[1..x-1]+A[x]となっているため、Replaceする場所のインデックスはx

コード:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cassert>
#include<climits>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
#define IINF (INT_MAX)
#define MAX 100

using namespace std;

struct P
{
  char opr,value;
  int pos;
  P(char opr = 'x',int pos=IINF,char value='x'):opr(opr),pos(pos),value(value){}
};

string from,to;
int dp[MAX][MAX];
char path[MAX][MAX];

int getPath(int x,int y)
{
  if(x == 0 && y == 0)
    {
      return 1;
    }
  if(x < 0 || y < 0)  
    {
      return 1;
    }
  if(path[y][x] == 'x')
    {
      return 1;
    }
  
  char c = path[y][x];
  
  int idx;
  if(c == 'i')
    {
      idx = getPath(x-1,y);
      cout << idx << " Insert " << x << "," << to[x-1] << endl;
    }
  else if(c == 'r')
    {
      idx = getPath(x-1,y-1);
      if(from[y-1] == to[x-1])return idx;
      cout << idx << " Replace " << x << "," << to[x-1] << endl;
    }
  else if(c == 'd')
    {
      idx = getPath(x,y-1);
      cout << idx << " Delete " << x+1 << endl;
    }
  return idx + 1;
}

void compute()
{
  int h = from.size(), w = to.size();

  rep(i,h+1)rep(j,w+1)path[i][j] = 'x';
  rep(i,h+1)
    {
      dp[i][0] = i;
      path[i][0] = 'd';
    }
  rep(i,w+1)
    {
      dp[0][i] = i;
      path[0][i] = 'i';
    }

  REP(y,1,h+1)
    {
      REP(x,1,w+1)
	{
	  int cost = !(from[y-1] == to[x-1]);
	  int cost_insert = dp[y][x-1] + 1;
	  int cost_delete = dp[y-1][x] + 1;
	  int cost_replace = dp[y-1][x-1] + cost;
	  int mincost = min(cost_insert,
			    min(cost_delete,cost_replace));

	  if(mincost == cost_replace)
	    {
	      path[y][x] = 'r';
	    }
	  else if(mincost == cost_delete)
	    {
	      path[y][x] = 'd';
	    }
	  else if(mincost == cost_insert)
	    {
	      path[y][x] = 'i';
	    }
	  else assert(false);

	  dp[y][x] = mincost;
	}
    }

  cout << dp[h][w] << endl;
  getPath(w,h);  
}

int main()
{
  bool first = true;
  while(getline(cin,from))
    {
      getline(cin,to);
      if(!first)puts("");
      first = false;
      compute();
    }
  return 0;
}