實機體驗,再天天抽M8金豪禮★拿現金最實在!這畫面也太叫人垂涎���滴!買太多也不行!7500...
2012-11-11 14:25:42 人氣(270) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA][dp] 526 - String Distance and Transform Process

0
收藏
0
推薦


  String Distance and Transform Process 

String Distance is a non-negative integer that measures the distance between two strings. Here we give the definition. A transform list is a list of strings, where each string, except for the last one, can be changed to the string followed by adding a character, deleting a character or replacing a character. The length of a transform list is the count of strings minus 1 (that is the count of operations to transform these two strings). The distance between two strings is the length of a transform list from one string to the other with the minimal length. You are to write a program to calculate the distance between two strings and give the corresponding transform list.

Input 

Input consists a sequence of string pairs, each string pair consists two lines, each string occupies one line. The length of each string will be no more than 80.

Output 

For each string pair, you should give an integer to indicate the length between them at the first line, and give a sequence of command to transform string1 to string 2. Each command is a line lead by command count, then the command. A command must be


Insert
pos,value

Delete pos

Replace pos,value


where pos is the position of the string and pos should be between 1 and the current length of the string (in Insert command, pos can be 1 greater than the length), and value is a character. Actually many command lists can satisfy the request, but only one of them is required.

Print a blank line between consecutive datasets.

Sample Input 

abcac
bcd
aaa
aabaaaa

Sample Output 

3
1 Delete 1
2 Replace 3,d
3 Delete 4

4
1 Insert 1,a
2 Insert 2,a
3 Insert 3,b
4 Insert 7,a



Miguel A. Revilla
1999-01-11
演算法剛教,馬上拿出來實作!!

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define maxN 100
using namespace std;
int dp[maxN][maxN], lx, ly;
int arg_dp[maxN][maxN];
char x[maxN], y[maxN];
int step, cont = 0;
void print(int i, int j) {
    if(i == 0 && j == 0)
        return;
    if(arg_dp[i][j] == -1) {
        print(i-1, j-1);
    } else if(arg_dp[i][j] == -2) {
        print(i-1, j-1);
        printf("%d Replace %d,%c\n", ++step, i-cont, y[j-1]);
    } else if(arg_dp[i][j] == -3) {
        print(i-1, j);
        printf("%d Delete %d\n", ++step, i-cont);
        cont++;
    } else if(arg_dp[i][j] == -4) {
        print(i, j-1);
        cont--;
        printf("%d Insert %d,%c\n", ++step, i-cont, y[j-1]);
    }
}
int main() {
    int i, j, first = 0;
    while(gets(x)) {
        gets(y);
        if(first)
            puts("");
        first = 1;
        lx = strlen(x), ly = strlen(y);
        for(i = 0; i <= lx; i++) {
            for(j = 0; j <= ly; j++) {
                dp[i][j] = 0xffff;
            }
        }
        dp[0][0] = 0;
        int cost[4] = {0,1,1,1};
        for(i = 0; i <= lx; i++) {
            for(j = 0; j <= ly; j++) {
                //copy
                if(x[i] == y[j]) {
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+cost[0]);
                    if(dp[i+1][j+1] == dp[i][j]+cost[0])
                        arg_dp[i+1][j+1] = -1;
                }
                //replace
                if(x[i] != y[j]) {
                    dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+cost[1]);
                    if(dp[i+1][j+1] == dp[i][j]+cost[1])
                        arg_dp[i+1][j+1] = -2;
                }
                //delete
                dp[i+1][j] = min(dp[i+1][j], dp[i][j]+cost[2]);
                if(dp[i+1][j] == dp[i][j]+cost[2])
                    arg_dp[i+1][j] = -3;
                //insert
                dp[i][j+1] = min(dp[i][j+1], dp[i][j]+cost[3]);
                if(dp[i][j+1] == dp[i][j]+cost[3])
                    arg_dp[i][j+1] = -4;
            }
        }
        printf("%d\n", dp[lx][ly]);
        step = cont = 0;
        print(lx, ly);
    }
    return 0;
}

526String Distance andTransform ProcessDP
台長:Morris
人氣(270) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][Trie] 12506 - Shortest Names
此分類上一篇:[UVA] 12527 - Different Digits

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文