編輯距離，又稱Levenshtein距離，是指兩個(gè)字串之間，由一個(gè)轉(zhuǎn)成另一個(gè)所需的最少編輯操作次數(shù)。許可的編輯操作包括將一個(gè)字符替換成另一個(gè)字符，插入一個(gè)字符，刪除一個(gè)字符。
　　以上的問(wèn)題可以用眾所周知的動(dòng)態(tài)規(guī)劃解決，現(xiàn)在的問(wèn)題是：如果新加入一種編輯操作：交換相鄰的兩個(gè)字符；求兩個(gè)字符串之間的編輯距離。

#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;;

}

無(wú)法 AC，但是找不到錯(cuò)誤，先記下。
http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1093

posted @ 2011-03-04 22:41 unixfy 閱讀(768) | 評(píng)論 (0) | 編輯收藏

C++ 博客的第一篇

剛剛開通 C++ 博客
本來(lái)有一個(gè)博客，為了提高專業(yè)性和擴(kuò)大交流面，特在此開通一個(gè)

這里將記述我的計(jì)算機(jī)方面的學(xué)習(xí)、研究、工作以及生活等
包括
程序設(shè)計(jì)語(yǔ)言
數(shù)據(jù)結(jié)構(gòu)與算法
自然語(yǔ)言處理
信息抽取
還有其他的計(jì)算機(jī)方面

還有我的生活

以上，2010-09-25

posted @ 2010-09-25 15:15 unixfy 閱讀(146) | 評(píng)論 (0) | 編輯收藏

僅列出標(biāo)題

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

常用鏈接

留言簿(3)

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜