查找字符串数组的公共前缀

php string algorithm

2022-08-30 22:37:13

我有一个这样的数组：

$sports = array(
'Softball - Counties',
'Softball - Eastern',
'Softball - North Harbour',
'Softball - South',
'Softball - Western'
);

我想找到字符串的最长公共前缀。在这种情况下，它将是'Softball - '

我想我会遵循这个过程

$i = 1;

// loop to the length of the first string
while ($i < strlen($sports[0]) {

  // grab the left most part up to i in length
  $match = substr($sports[0], 0, $i);

  // loop through all the values in array, and compare if they match
  foreach ($sports as $sport) {

     if ($match != substr($sport, 0, $i) {
         // didn't match, return the part that did match
         return substr($sport, 0, $i-1);
     }

  } // foreach

   // increase string length
   $i++;
} // while

// if you got to here, then all of them must be identical

问题

是否有内置函数或更简单的方法来执行此操作？
对于我的5行数组来说，这可能很好，但是如果我要做几千个行数组，会有很多开销，所以我必须用我的起始值移动，例如=字符串的一半，如果它失败了，那么直到它工作，然后递增1直到我们成功。因此，我们正在进行最少数量的比较以获得结果。$i$i$i/2$i

对于这类问题，有没有一个公式/算法已经存在？

答案 1

如果您可以对数组进行排序，那么有一个简单且非常快速的解决方案。

只需将第一项与最后一项进行比较即可。

如果对字符串进行排序，则所有字符串通用的任何前缀对于排序后的第一个和最后一个字符串将是通用的。

sort($sport);

$s1 = $sport[0];               // First string
$s2 = $sport[count($sport)-1]; // Last string
$len = min(strlen($s1), strlen($s2));

// While we still have string to compare,
// if the indexed character is the same in both strings,
// increment the index. 
for ($i=0; $i<$len && $s1[$i]==$s2[$i]; $i++); 

$prefix = substr($s1, 0, $i);

答案 2

我会用这个：

$prefix = array_shift($array);  // take the first item as initial prefix
$length = strlen($prefix);
// compare the current prefix with the prefix of the same length of the other items
foreach ($array as $item) {
    // check if there is a match; if not, decrease the prefix by one character at a time
    while ($length && substr($item, 0, $length) !== $prefix) {
        $length--;
        $prefix = substr($prefix, 0, -1);
    }
    if (!$length) {
        break;
    }
}

更新这是另一种解决方案，以迭代方式比较字符串的每个 n 个字符，直到发现不匹配：

$pl = 0; // common prefix length
$n = count($array);
$l = strlen($array[0]);
while ($pl < $l) {
    $c = $array[0][$pl];
    for ($i=1; $i<$n; $i++) {
        if ($array[$i][$pl] !== $c) break 2;
    }
    $pl++;
}
$prefix = substr($array[0], 0, $pl);

这甚至更有效，因为最多只有数量OfStrings ·commonPrefixLength 原子比较。