题目描述
题目要求计算两个字符串之间的编辑距离（Levenshtein distance\texttt{Levenshtein distance}Levenshtein distance），并输出具体的编辑操作序列。允许的操作有：
- Delete pos\texttt{Delete pos}Delete pos：删除位置pospospos的字符。
- Insert pos,value\texttt{Insert pos,value}Insert pos,value：在位置pospospos插入字符valuevaluevalue。
- Replace pos,value\texttt{Replace pos,value}Replace pos,value：将位置pospospos的字符替换为valuevaluevalue。
输出格式：第一行为编辑距离，接下来每行一个操作（按执行顺序编号）。两个连续测试用例的输出之间由一个空行分隔。
输入格式
输入包含多个字符串对，每对由两行组成，每行一个字符串（长度不超过808080）。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每个字符串对，输出编辑距离，然后输出操作序列。不同测试用例的输出之间由一个空行分隔。
样例
输入
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题目分析
本题的核心是计算最小编辑距离并回溯输出操作序列。
动态规划
定义dp[i][j]\textit{dp}[i][j]dp[i][j]为将SSS的前iii个字符转换为TTT的前jjj个字符所需的最小操作数。转移方程：
- 删除：dp[i][j]=dp[i−1][j]+1\textit{dp}[i][j] = \textit{dp}[i-1][j] + 1dp[i][j]=dp[i−1][j]+1
- 插入：dp[i][j]=dp[i][j−1]+1\textit{dp}[i][j] = \textit{dp}[i][j-1] + 1dp[i][j]=dp[i][j−1]+1
- 替换：dp[i][j]=dp[i−1][j−1]+1\textit{dp}[i][j] = \textit{dp}[i-1][j-1] + 1dp[i][j]=dp[i−1][j−1]+1（若S[i]≠T[j]S[i] \ne T[j]S[i]=T[j]）
- 匹配：dp[i][j]=dp[i−1][j−1]\textit{dp}[i][j] = \textit{dp}[i-1][j-1]dp[i][j]=dp[i−1][j−1]（若S[i]=T[j]S[i] = T[j]S[i]=T[j]）
同时记录每个状态的操作类型，以便回溯。
操作序列回溯
从(M,N)(M, N)(M,N)回溯到(0,0)(0, 0)(0,0)，根据记录的操作类型逆序输出。注意：
- 删除操作会影响后续字符的位置，因此输出时需要动态调整位置索引。
- 插入操作同理。
- 替换操作不改变位置索引。
复杂度分析
时间复杂度O(M×N)O(M \times N)O(M×N)，空间复杂度O(M×N)O(M \times N)O(M×N)，M,N≤80M, N \le 80M,N≤80，可接受。
代码实现
// String Distance and Transform Process// UVa ID: 526// Verdict: Accepted// Submission Date: 2016-02-13// UVa Run Time: 0.009s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintNONE=-1,DELETE=0,INSERT=1,CHANGE=2,MATCH=3;// 定义动态规划表格单元。structcell{intcost,operation;};cell dp[100][100];string S,T,operationCode[3]={" Delete "," Insert "," Replace "};intM,N,deletions,insertions,indexer;// 显示操作步骤，注意删除操作其序号会因为已有的删除和插入操作而发生变化。voiddisplayPath(inti,intj){if(dp[i][j].operation>=DELETE&&dp[i][j].operation<=CHANGE){cout<<indexer++;cout<<operationCode[dp[i][j].operation];if(dp[i][j].operation==CHANGE){cout<<j<<","<<T[j]<<"\n";}elseif(dp[i][j].operation==DELETE){cout<<(i+insertions-deletions)<<"\n";deletions++;}elseif(dp[i][j].operation==INSERT){cout<<j<<","<<T[j]<<"\n";insertions++;}}}// 利用递归构建操作步骤。voidfindPath(inti,intj){if(dp[i][j].operation!=NONE){if(dp[i][j].operation==DELETE)findPath(i-1,j);elseif(dp[i][j].operation==INSERT)findPath(i,j-1);elsefindPath(i-1,j-1);}displayPath(i,j);}voidminimumEditDistance(){// 为每个字符串起始位置增加一个空格，将字符串序号和表格序号对齐，方便处理。// 因此其长度需要相应减去 1。S=' '+S;T=' '+T;M=S.length()-1;N=T.length()-1;dp[0][0]=(cell){0,NONE};for(inti=1;i<=M;i++)dp[i][0]=(cell){i,DELETE};for(intj=1;j<=N;j++)dp[0][j]=(cell){j,INSERT};// 自底向上动态规划求解。for(inti=1;i<=M;i++)for(intj=1;j<=N;j++){dp[i][j]=(cell){dp[i-1][j].cost+1,DELETE};if(dp[i][j].cost>(dp[i][j-1].cost+1))dp[i][j]=(cell){dp[i][j-1].cost+1,INSERT};if(S[i]==T[j]){if(dp[i][j].cost>dp[i-1][j-1].cost)dp[i][j]=(cell){dp[i-1][j-1].cost,MATCH};}else{if(dp[i][j].cost>(dp[i-1][j-1].cost+1))dp[i][j]=(cell){dp[i-1][j-1].cost+1,CHANGE};}}// 反向构建操作步骤。deletions=0;insertions=0;indexer=1;cout<<dp[M][N].cost<<"\n";findPath(M,N);}intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);boolprintBlankLine=false;while(getline(cin,S)&&getline(cin,T)){if(printBlankLine==false)printBlankLine=true;elsecout<<"\n";minimumEditDistance();}return0;}