计算字符串的相似度

计算字符串的相似度

我们定义了一套操作方法来把两个不相同的字符串变得相同，具体的操作方法为：

1. 修改一个字符 （如 把“a”替换为“b”）。

2. 增加一个字符 （如把“abdd”变为“aebdd”）。

3. 删除一个字符（如把“travelling”变为“traveling”）。

比如，对于“abcdefg”和“abcdef”两个字符串来说，我们认为可以通过增加/减少一个“g” 的方式来达到目的。上面的两种方案，都仅需要一次操作。把这个操作所需要的次数定义为两个字符串的距离，而相似度等于“距离+1”的倒数。

分析与解法

1. 一步操作之后，再将A[2, …, lenA]和B[1, …, lenB]变成相同字符串。

2. 一步操作之后，再将A[1, …, lenA]和B[2, …, lenB]变成相同字符串。

3. 一步操作之后，再将A[2, …, lenA]和B[2, …, lenB]变成相同字符串。

int CalculateStringDistance(string strA, int pABegin, int pAEnd, string strB,int pBBegin, int pBEnd){

      if(pABegin>pAEnd){

            if(pBBegin>pBEnd)

                  return 0;

            else

                  return pBEnd-pBBegin+1;

     

      }

      if(pBBegin > pBEnd)

      {

            if(pABegin > pAEnd)

                  return 0;

            else

                  return pAEnd – pABegin + 1;

      }

      if(strA[pABegin]==strB[pBBegin])

return CalculateStringDistance(strA, pABegin+1, pAEnd, strB, pBBegin+1, pBEnd);

      else{

int t1 = CalculateStringDistance(strA, pABegin + 1, pAEnd, strB, pBBegin + 2, pBEnd);

int t2 = CalculateStringDistance(strA, pABegin + 2, pAEnd, strB, pBBegin + 1, pBEnd);

int t3 = CalculateStringDistance(strA, pABegin + 2, pAEnd, strB, pBBegin + 2, pBEnd);

            return minValue(t1,t2,t3) + 1;     

       }
}