UVa 526 String Distance and Transform Process

题目描述题目要求计算两个字符串之间的编辑距离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//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constintNONE-1,DELETE0,INSERT1,CHANGE2,MATCH3;// 定义动态规划表格单元。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].operationDELETEdp[i][j].operationCHANGE){coutindexer;coutoperationCode[dp[i][j].operation];if(dp[i][j].operationCHANGE){coutj,T[j]\n;}elseif(dp[i][j].operationDELETE){cout(iinsertions-deletions)\n;deletions;}elseif(dp[i][j].operationINSERT){coutj,T[j]\n;insertions;}}}// 利用递归构建操作步骤。voidfindPath(inti,intj){if(dp[i][j].operation!NONE){if(dp[i][j].operationDELETE)findPath(i-1,j);elseif(dp[i][j].operationINSERT)findPath(i,j-1);elsefindPath(i-1,j-1);}displayPath(i,j);}voidminimumEditDistance(){// 为每个字符串起始位置增加一个空格将字符串序号和表格序号对齐方便处理。// 因此其长度需要相应减去 1。S S;T T;MS.length()-1;NT.length()-1;dp[0][0](cell){0,NONE};for(inti1;iM;i)dp[i][0](cell){i,DELETE};for(intj1;jN;j)dp[0][j](cell){j,INSERT};// 自底向上动态规划求解。for(inti1;iM;i)for(intj1;jN;j){dp[i][j](cell){dp[i-1][j].cost1,DELETE};if(dp[i][j].cost(dp[i][j-1].cost1))dp[i][j](cell){dp[i][j-1].cost1,INSERT};if(S[i]T[j]){if(dp[i][j].costdp[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].cost1))dp[i][j](cell){dp[i-1][j-1].cost1,CHANGE};}}// 反向构建操作步骤。deletions0;insertions0;indexer1;coutdp[M][N].cost\n;findPath(M,N);}intmain(intargc,char*argv[]){cin.tie(0);cout.sync_with_stdio(false);boolprintBlankLinefalse;while(getline(cin,S)getline(cin,T)){if(printBlankLinefalse)printBlankLinetrue;elsecout\n;minimumEditDistance();}return0;}