久久精品国产96久久久香蕉,亚洲第一在线综合在线,亚洲欧洲精品天堂一级

編輯距離 + 交換操作

編輯距離，又稱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 閱讀(765) 評論(0) 編輯收藏引用

常用鏈接

留言簿(3)

隨筆檔案

搜索

最新評論

閱讀排行榜

評論排行榜

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！



網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理