String Distance and Transform Process 상세 정보

제목: 두 문자열str1,str2.str1이str2와 일치하도록 합니다.str1을 증가, 삭제, 고칠 수 있습니다.
Insert pos,value Delete pos Replace pos,value 
샘플 입력:

abcac
bcd
aaa
aabaaaa

출력 예제:

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

방법: 동적 계획
1. dp[i][j], i는str1의 i위, j는str2의,str1[i-1],str[j-1]가 일치하는 후 몇 걸음이 필요한지 표시
2. dp[x][y]=min(dp[x-1][y]+1, dp[x][y-1]+1, dp[x-1][y-1]+(str1[i-1]과str2[j-1]가 같은지 안 같은지는 조작(고칠 필요가 없고, 다르면 고칠 필요가 있다)).
3. 경계 조건:str1 길이가 0일 때 dp[0][str2.size()]는str2가 필요합니다.size()보(str2.size()회 증가);
4. 반복 순서: asc(순서)
참고:
1.dp[str1.size()][str2.size()];//오류 설명: dp[len1][len2];
2. 첨삭 수정.고치는 것이 증가하는 것보다 낫고, 고치는 것이 삭제하는 것보다 낫다.
불친절한 코드는 다음과 같습니다.

#include 
#include 
#include <string>
#include 
using namespace std;

#define xx 81

int min(int x, int y, int z) {
    x = x < y ? x : y;
    return x < z ? x : z;
}

int main() {
    string str1, str2;
    int dp[xx][xx];
    bool flag[xx][xx];
    int len1, len2;

    while (cin >> str1 >> str2) {
        len1 = str1.size(), len2 = str2.size();
        //cout << len1 << "     " << len2 << endl;
        //  flag
        for (int i = 0; i < len1; i++)
            for (int j = 0; j < len2; j++)
                flag[i][j] = str1[i] == str2[j] ? 0 : 1;
        //    
        for (int i = 0; i < xx; ++i)dp[i][0] = dp[0][i] = i;
        //  dp
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + flag[i-1][j-1]);//     
            }
        }
        //  
        cout << dp[len1][len2] << "
";
        for (int k = 1; k <= dp[str1.size()][str2.size()];) {
            int t;
            if (len1 == 0 && len2 != 0)t = 1;
            else if (len1 != 0 && len2 == 0)t = 2;
            else if (len1 != 0 && len2 != 0) {
                /*
                if (dp[len1][len2 - 1] == min(dp[len1 - 1][len2], dp[len1][len2 - 1], dp[len1 - 1][len2 - 1]))t = 1;// 
                else if (dp[len1 - 1][len2] == min(dp[len1 - 1][len2], dp[len1][len2 - 1], dp[len1 - 1][len2 - 1]))t = 2;// 
                else if (dp[len1 - 1][len2 - 1] == min(dp[len1 - 1][len2], dp[len1][len2 - 1], dp[len1 - 1][len2 - 1]))t = (dp[len1 - 1][len2 - 1] == dp[len1][len2] ? 0 : 3);//   
                */
                //     ，     
                if (dp[len1 - 1][len2 - 1] == min(dp[len1 - 1][len2], dp[len1][len2 - 1], dp[len1 - 1][len2 - 1]))t = (dp[len1 - 1][len2 - 1] == dp[len1][len2] ? 0 : 3);//   
                else if (dp[len1][len2 - 1] == min(dp[len1 - 1][len2], dp[len1][len2 - 1], dp[len1 - 1][len2 - 1]))t = 1;// 
                else if (dp[len1 - 1][len2] == min(dp[len1 - 1][len2], dp[len1][len2 - 1], dp[len1 - 1][len2 - 1]))t = 2;// 
            }
            //cout << k << "     " << dp[str1.size()][str2.size()] << endl;
            //cout << len1 << len2 << endl;
            switch (t) {
            case 0:len1--, len2--;break;//  
            case 1:printf("%d Insert %d,%c
", k++, len1 + 1, str2[--len2]);break;// 
            case 2:printf("%d Delete %d
", k++, len1--);break;// 
            case 3:printf("%d Replace %d,%c
", k++, len1--, str2[--len2]);break;// 
            default:break;
            }

        }
        //cout << " over " << endl;

    }
    return 0;
}

개인적으로 제 문제풀이만 보시고 코드는 제가 쓰세요~ 제가 머리가 커요.