# HDU-1516 编辑距离
## [HDU-1516](http://acm.hdu.edu.cn/showproblem.php?pid=1516)
## 问题描述
典型模板题, 编辑距离.
利用LCS相似方法进行DP, 之后再进行逆推求得序列.
## 转移方程
$$
dp[i][j] = \begin{cases}
i, &j=0 \\
j, &i=0 \\
min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]), &str1[i-1] = str2[j-1] \\
min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1] + 1), &str1[i-1] \ne str2[j-1] \\
\end{cases}
$$
min中的三项分别代表在str1中**删除**, **插入**, **替换(或不变)**.
## 通过DP矩阵逆推结果
当$dp[i][j]$不为0时, 意味着两字符串没有完全相同, 需要继续推导:
- 若$a[i-1]=b[j-1] 且 dp[i][j]=dp[i-1][j-1]$: 两串在此字符处相等, 因此向左上方继续推导
- 若$a[i-1] \ne b[j-1] 且 dp[i][j]=dp[i-1][j-1]+1$: 两串在这里是替换关系, 因此记录一条替换, 向左上方继续推导
- 若$dp[i][j]=dp[i-1][j]+1$: a串需要删除掉该字符, 向上方继续推导
- 若$dp[i][j]=dp[i][j-1]+1$: a串需要插入该字符, 向左方继续推导
因为这四个判断发生的顺序可以不同, 因此会产生多个结果. 一般来讲只需任意输出一个即可.
## 代码
```cpp
// -------------- GLOBAL ----------------
string a, b;
int alen, blen;
int dp[100][100] = {0};
// -------------- FUNC ----------------
void prt() {
F0(i, alen + 1) {
F0(j, blen + 1) {
cout << setw(3) << dp[i][j];
}
cout << endl;
}
}
void doDP() {
F1(i, alen) {
F1(j, blen) {
int dodelete = dp[i - 1][j] + 1;
int doinsert = dp[i][j - 1] + 1;
int doreplace = dp[i - 1][j - 1] + (a[i - 1] != b[j - 1]);
dp[i][j] = min(min(dodelete, doinsert), doreplace);
}
}
}
void initDP() {
fill0(dp);
F1(i, alen) {
dp[i][0] = i;
}
F1(j, blen) {
dp[0][j] = j;
}
}
void doRes() {
int i = alen, j = blen, cnt = 0;
cout << dp[alen][blen] << endl;
while (dp[i][j]) {
int t = (a[i - 1] != b[j - 1]);
if (i > 0 && j > 0 && dp[i][j] == dp[i - 1][j - 1] + t) {
if (t)
cout << ++cnt << " Replace " << i << "," << b[j - 1] << endl;
i--;
j--;
} else if (i > 0 && dp[i][j] == dp[i - 1][j] + 1) {
cout << ++cnt << " Delete " << i << endl;
i--;
} else {
cout << ++cnt << " Insert " << i + 1 << "," << b[j - 1] << endl;
j--;
}
}
}
// -------------- MAIN ----------------
int main() {
ios_base::sync_with_stdio(false);
while (cin >> a >> b) {
alen = a.length();
blen = b.length();
initDP();
doDP();
// prt();
doRes();
}
return 0;
}
```
![]()