最新消息:yaf表单扩展中新增加了浮点数、日期和集合的校验。php yaf框架扩展实践三——表单

用C语言实现计算两个字符串的汉明距离

C语言 6134浏览 0评论

在庞果网上看到计算两个字符串的汉明距离问题,要求用java实现。自己不熟悉java,就想着用c尝试下。汉明距离就是两个等长字符串对应位置的不同字符的个数。例如:

  • “toned”和”roses”的汉明距离是3。
  • 1011101和1001001的汉明距离是2。
  • 2173896和2233796的汉明距离是3。

c语言的实现代码:

int hamdist(char *a, char *b)
{
    int dist = 0;

    while (*a && *b) {
        dist += (*a != *b) ? 1 : 0;
        *a++;
        *b++;
    }

    return dist;
}

这里没有考虑两个字符串长度不一致的情况,如果长度不一致则涉及到编辑距离,关于编辑距离维基百科上有相关说明,这里就不介绍了。该方法的执行时间由字符串长度决定,时间复杂度是O(n)。用两个字符串来测试一下:

#include <stdio.h>

int main()
{
    char *a, *b;
    a = "00001001000001110000000000100001";
    b = "00101000000101110000010000100001";

    int dist = hamdist(a, b);
    //输出4
    printf("%d\n", dist);

    return 0;
}

另外如果要计算两个整数的二进制的汉明距离,可以使用如下方法,效率更高。

int hamdist(int a, int b)
{
    int dist = 0, val = a ^ b;
    printf("%d\n", val);
    while (val) {
        ++dist;
        val &= val - 1;
    }

    return dist;
}

这边while循环的次数其实就是汉明距离。

小结

汉明距离是以理查德·卫斯里·汉明的名字命名的,有兴趣的朋友可以了解下这位先辈。除了汉明距离,还有汉明重量、汉明码等理论在信息论、编码理论、密码学等领域都有应用。

转载请注明:快乐编程 » 用C语言实现计算两个字符串的汉明距离

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址