posts - 183,  comments - 10,  trackbacks - 0
编辑距离 + 交换操作
编辑距离，又称Levenshtein距离，是指两个字串之间，由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
　　以上的问题可以用众所周知的动态规划解决，现在的问题是：如果新加入一种编辑操作：交换相邻的两个字符；求两个字符串之间的编辑距离。
#include <iostream>
#include <cstring>
using namespace std;

#define T(t) cout << #t": " << t << endl;

int a[1002][1002];
char s1[1002], s2[1002];

int main()
{
    cin >> s1 >> s2;
    for (int i = 0; i < 1002; ++i) {
        a[i][0] = i;
        a[0][i] = i;
    }
    int n1 = strlen(s1), n2 = strlen(s2);
    int r, t, c1;
    for (int i = 1; i <= n1; ++i) {
        for (int j = 1; j <= n2; ++j) {
            r = (a[i-1][j] < a[i][j-1] ? a[i-1][j] : a[i][j-1]) + 1;
            if (s1[i-1] != s2[j-1]) {
                t = a[i-1][j-1] + 1;
            }
            else {
                t = a[i-1][j-1];
            }
            r = (r < t ? r : t);    
            if (i >= 2 && j >= 2) {
                c1 = a[i-2][j-2] + 1;
                r = (r < c1 ? r : c1);
            }
            a[i][j] = r;
        }
    }
    cout << a[n1][n2] << endl;;
}
无法 AC，但是找不到错误，先记下。
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1093
posted on 2011-03-04 22:41 unixfy 阅读(731) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理


Powered by:
C++博客
Copyright ©2024 unixfy