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

发布于 2024-08-03 14:07:37 字数 1057 浏览 7 评论 0原文

我有一个这样的数组：

$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行数组来说可能没问题，但是如果我要做几千行数组，会有很多开销，所以我必须用 $i 的起始值进行移动计算，例如 $i = 字符串的一半，如果失败，则 $i/2 直到成功，然后将 $i 加 1 直到成功。这样我们就可以通过最少的比较次数来获得结果。

是否已经有解决此类问题的公式/算法？

原文

I have an array like this:

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

I would like to find the longest common prefix of the string. In this instance, it would be 'Softball - '

I am thinking that I would follow this process

$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

For my 5 lines array that is probably fine, but if I were to do several thousand lines arrays, there would be a lot of overhead, so I would have to be move calculated with my starting values of $i, eg $i = halfway of string, if it fails, then $i/2 until it works, then increment $i by 1 until we succeed. So that we are doing the least number of comparisons to get a result.

Is there a formula/algorithm out already out there for this kind of problem?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

感情废物 2024-08-10 14:07:37

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

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

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

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);

If you can sort your array, then there is a simple and very fast solution.

Simply compare the first item to the last one.

If the strings are sorted, any prefix common to all strings will be common to the sorted first and last strings.

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);

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

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

评论（16）

以尽可能少的迭代次数获取数组中字符串的最大公共前缀（PHP）

Get the maximum common prefix of strings in an array with as little iterations as possible (PHP)

关于作者

相关话题

热门标签

推荐作者

留蓝

18790681156

zach7772

Wini

ayeshaaroy

初雪

友情链接

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。