查找两个字符串之间不同的第一个字符

一尘不染

查找两个字符串之间不同的第一个字符

php

给定两个相等长度的字符串，是否有一种优雅的方法来获取第一个不同字符的偏移量？

显而易见的解决方案是：

for ($offset = 0; $offset < $length; ++$offset) {
    if ($str1[$offset] !== $str2[$offset]) {
        return $offset;
    }
}

但这对于如此简单的任务而言似乎并不正确。

阅读 464

2020-05-29

共1个答案

一尘不染

您可以使用按位XOR（^）的一个不错的属性来实现此目的：基本上，当您将两个字符串异或时，相同的字符将变为空字节（"\0"）。因此，如果我们对两个字符串进行异或运算，我们只需要使用以下命令找到第一个非空字节的位置strspn：

$position = strspn($string1 ^ $string2, "\0");

这里的所有都是它的。因此，让我们看一个例子：

$string1 = 'foobarbaz';
$string2 = 'foobarbiz';
$pos = strspn($string1 ^ $string2, "\0");

printf(
    'First difference at position %d: "%s" vs "%s"',
    $pos, $string1[$pos], $string2[$pos]
);

将会输出：

位置7的第一个区别：“ a”与“ i”

所以应该这样做。这是非常有效的，因为它仅使用C函数，并且仅需要字符串存储的单个副本。

编辑：沿同一行的多字节解决方案：

function getCharacterOffsetOfDifference($str1, $str2, $encoding = 'UTF-8') {
    return mb_strlen(
        mb_strcut(
            $str1,
            0, strspn($str1 ^ $str2, "\0"),
            $encoding
        ),
        $encoding
    );
}

首先使用上述方法找到字节级别的差异，然后将偏移量映射到字符级别。这是通过使用mb_strcut函数完成的，该函数基本上是在substr尊重多字节字符边界。

var_dump(getCharacterOffsetOfDifference('foo', 'foa')); // 2
var_dump(getCharacterOffsetOfDifference('©oo', 'foa')); // 0
var_dump(getCharacterOffsetOfDifference('f©o', 'fªa')); // 1

它不像第一个解决方案那样优雅，但是仍然是单一的（如果使用默认编码则更简单）：

return mb_strlen(mb_strcut($str1, 0, strspn($str1 ^ $str2, "\0")));

2020-05-29