论坛 › 源码分享 › 计算字符串相似度

元始天尊 发表于 2014-9-2 22:42:58

计算字符串相似度

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

代码为：

#include <iostream>
using namespace std;

#define min(x,y) ((x<y)?x:y)
#define arr(x,y) arr[(x)*size2+(y)]

void main()
{
        char s1[]="xfdfa";
        char s2[]="xabcdae";

        int size1=sizeof(s1)-1;
        int size2=sizeof(s2)-1;
        int* arr=new int;
        int i,j;

        //初始化角元
        bool matched=false;
        if(*s1 == *s2)
        {
                matched=true;
                arr(0,0)=0;
        }
        else
        {
                arr(0,0)=1;
        }

        //初始化首行
        for(i=1;i<size1;i++)
        {
                arr(i,0)=arr(i-1,0);
                if(!matched && (*s2 == s1))
                {
                        matched=true;
                }
                else
                {
                        arr(i,0)++;
                }
        }

        //初始化首列
        if(*s1 != *s2)
        {
                matched=false;
        }
        for(i=1;i<size2;i++)
        {
                arr(0,i)=arr(0,i-1);
                if(!matched && (*s1 == s2))
                {
                        matched=true;
                }
                else
                {
                        arr(0,i)++;
                }
        }

        for(i=1;i<size1;i++)
        {
                for(j=1;j<size2;j++)
                {
                        int t1=min(arr(i-1,j),arr(i,j-1));
                        int t2=arr(i-1,j-1);
                        if(s1 == s2)
                                t2--;
                        arr(i,j)=min(t1,t2)+1;
                }
        }

        cout<<arr(size1-1,size2-1)<<endl;

        delete []arr;
}

查看完整版本: 计算字符串相似度