计算字符串相似度

元始天尊

编程之美 3.3节计算字符串相似度问题我找到了一种非递归方式
题目要求为：可以通过增、删、替换三种方式作为一次改变，对于给定2个字符串，最少需要多少次变换可以变成另一个字符串。
应用动态规划方法：F[i,j]=min{F[i-1,j],F[i,j-1],temp}+1;
temp取值为：
F[i-1,j-1]    S1 != S2[j]
F[i-1,j-1]-1  S1 == S2[j]

代码为：

1. 
   
2. #include <iostream>
   
3. using namespace std;
   
4. 
   
5. #define min(x,y) ((x<y)?x:y)
   
6. #define arr(x,y) arr[(x)*size2+(y)]
   
7. 
   
8. void main()
   
9. {
   
10.         char s1[]="xfdfa";
    
11.         char s2[]="xabcdae";
    
12. 
    
13.         int size1=sizeof(s1)-1;
    
14.         int size2=sizeof(s2)-1;
    
15.         int* arr=new int[size1*size2];
    
16.         int i,j;
    
17. 
    
18.         //初始化角元
    
19.         bool matched=false;
    
20.         if(*s1 == *s2)
    
21.         {
    
22.                 matched=true;
    
23.                 arr(0,0)=0;
    
24.         }
    
25.         else
    
26.         {
    
27.                 arr(0,0)=1;
    
28.         }
    
29. 
    
30.         //初始化首行
    
31.         for(i=1;i<size1;i++)
    
32.         {
    
33.                 arr(i,0)=arr(i-1,0);
    
34.                 if(!matched && (*s2 == s1[i]))
    
35.                 {
    
36.                         matched=true;
    
37.                 }
    
38.                 else
    
39.                 {
    
40.                         arr(i,0)++;
    
41.                 }
    
42.         }
    
43. 
    
44.         //初始化首列
    
45.         if(*s1 != *s2)
    
46.         {
    
47.                 matched=false;
    
48.         }
    
49.         for(i=1;i<size2;i++)
    
50.         {
    
51.                 arr(0,i)=arr(0,i-1);
    
52.                 if(!matched && (*s1 == s2[i]))
    
53.                 {
    
54.                         matched=true;
    
55.                 }
    
56.                 else
    
57.                 {
    
58.                         arr(0,i)++;
    
59.                 }
    
60.         }
    
61. 
    
62.         for(i=1;i<size1;i++)
    
63.         {
    
64.                 for(j=1;j<size2;j++)
    
65.                 {
    
66.                         int t1=min(arr(i-1,j),arr(i,j-1));
    
67.                         int t2=arr(i-1,j-1);
    
68.                         if(s1[i] == s2[j])
    
69.                                 t2--;
    
70.                         arr(i,j)=min(t1,t2)+1;
    
71.                 }
    
72.         }
    
73. 
    
74.         cout<<arr(size1-1,size2-1)<<endl;
    
75. 
    
76.         delete []arr;
    
77. }
    

复制代码