Lowden

now

字符串编辑距离(C++实现,DPA算法)

 1 #include <string>
 2 #include <iostream>
 3 using namespace std;
 4 int b[51][51];//存储最小编辑距离
 5 int op[51][51];//存储转换操作
 6 int min(int x,int y,int z)
 7 {
 8  int temp;
 9  if(x<y)
10  {
11   temp=x;
12  }
13  else temp=y;
14  if(z<temp) temp=z;
15  return temp;
16 }
17 int opc(int x,int y,int z)
18 {
19  if(x<=y&&x<=z)return 1;
20  if(y<=x&&y<=z)return 2;
21  return 3;
22 }
23 int  editDistance(string s,string aim)
24 {
25  int sLength=s.length();
26  int aLength=aim.length();
27  
28  for(int i=1;i<=sLength;i++)
29  {
30   b[0][i]=i;
31   op[0][i]=2;
32  }
33  for(int k=1;k<=aLength;k++)
34  {
35   b[k][0]=k;
36   op[k][0]=1;
37  }
38  for(int j=1;j<=sLength;j++)
39  {
40   for(int i=1;i<=aLength;i++)
41   {
42    int x=b[i-1][j]+1;
43    int y=b[i][j-1]+1;
44    int z=b[i-1][j-1]+(s[j-1]==aim[i-1]?0:1);
45    b[i][j]=min(x,y,z);
46    op[i][j]=opc(x,y,z);
47   }
48  }
49  return b[aLength][sLength];
50 }
51 void printRes(string s,string aim)
52 {
53  int j=s.length();
54  int i=aim.length();
55  cout<<s<<endl;
56  while(j!=0||i!=0)
57  {
58   int x=op[i][j];
59   if(3==x)
60   {
61    if(s[j-1]!=aim[i-1])
62    {
63     s[j-1]=aim[i-1];
64     cout<<s<<endl;
65    }
66    i--,j--;
67    continue;
68   }
69   if(2==x)
70   {
71    s.erase(j-1,1);
72    j--;
73   }
74   else
75    if(1==x)
76    {
77     s.insert(s.begin()+j,1,aim[i-1]);
78     i--;
79    }
80   cout<<s<<endl;
81  }
82 }
83 int main()
84 {
85  string s;
86  string aim;
87  cin>>s>>aim;
88  int edit=editDistance(s,aim);
89     printRes(s,aim);
90  //cout<<edit<<endl;
91  return 0;
92 }
93 

posted on 2010-11-18 16:45 Lowden 阅读(383) 评论(0)  编辑  收藏


只有注册用户登录后才能发表评论。
网站导航:

My Links

Blog Stats

常用链接

留言簿

随笔分类

随笔档案

文章分类

文章档案

好友链接

搜索

最新评论

阅读排行榜

评论排行榜