程式碼備份區

題意：

給兩個字串，要用最少的步驟把第一個字串變成第二個字串

這題跟UVA164一模一樣，只要改掉IO即可

這題可能會出現空字串，所以要用gets()去吃字串

解法：

Edit distance找出最少步驟，再去印出步驟

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MIN(x,y)(((x)<(y))?(x):(y))
char a[100]="#";
char b[100]="#";

int dp[100][100];
int s = 1;

int findDp(int i,int j){
    if(dp[i][j]==-1){
        if(i*j==0)dp[i][j] = i+j;
        else if(a[i]==b[j]){
            dp[i][j] = findDp(i-1,j-1);
        }else{
            dp[i][j] = MIN(findDp(i-1,j-1),MIN(findDp(i-1,j),findDp(i,j-1)))+1;
        }
    }
    return dp[i][j];
}

void printA(int i,int j){
    if(i*j==0){
        while(i>0){
            printf("%d Delete %d\n",s++,i);
            --i;
        }
        while(j>0){
            printf("%d Insert %d,%c\n",s++,i+1,b[j]);
            --j;
        }
    }else if(a[i]==b[j]){
        printA(i-1,j-1);
    }else{
        if(dp[i][j]-1 == dp[i-1][j-1]){
            printf("%d Replace %d,%c\n",s++,i,b[j]);
            printA(i-1,j-1);
        }else if(dp[i][j]-1 == dp[i][j-1]){
            printf("%d Insert %d,%c\n",s++,i+1,b[j]);
            printA(i,j-1);
        }else if(dp[i][j]-1 == dp[i-1][j]){
            printf("%d Delete %d\n",s++,i);
            printA(i-1,j);
        }
    }
}

int main(){
    int f=0;
    while(gets(&a[1])){
        if(f)puts("");
        else f=1;
        gets(&b[1]);
        s = 1;
        memset(dp,-1,sizeof(dp));
        printf("%d\n",findDp(strlen(a)-1,strlen(b)-1));
        printA(strlen(a)-1,strlen(b)-1);
    }

    return 0;
}