求两个字符串的相似度（或距离）

http://hi.baidu.com/erennetwork/blog/item/abe65068b92a81c980cb4a58.html

两个字符串距离和相似度的定义：

通过修改、增加和删除操作，使两个字符串变的相等，所做的操作次数为两个字符串的距离，距离加1的倒数为相似度。

例如：

A = "abeg";

B = "cdeg";

通过更改A中的ab=>cd使两个字符串相等，两个操作，距离为2。

求距离的代码如下：

int calDistance(char *A, char *B)
{
if(*A == '\0')//如果A结束了，则可以通过给A增加strlen(B)个字符使其相等。
{
return strlen(B);
}
if(*B == '\0')//如果B结束了，则可以通过给A增加strlen(A)个字符使其相等。
{
return strlen(A);
}
if(*A == *B)//如果这两个字符相等，则考虑后面的。
{
return calDistance(A+1,B+1);
}
else//如果这两个字符不相等，则可有三种操作使其相等，取所需操作最少的那个。
{
int temp1 = calDistance(A+1, B);//操作1：给B增加一个字符
int temp2 = calDistance(A, B+1);//操作2：给A增加一个字符
int temp3 = calDistance(A+1,B+1);//操作3：更改一个字符
if(temp1 > temp2)
temp1 = temp2;
if(temp1 > temp3)
temp1 = temp3;
return temp1+1;//因为这一步有一个操作，所以+1
}
}