最长公共前缀(Longest Common Prefix): 从多行字符串中找出最长相同的前缀
实现一：竖向扫描
代码语言：javascript复制<?php
/**
* 最长公共前缀实现(竖向扫描)
* @author Feei(wufeifei@wufeifei.com)
* @date 2012.04.23
*/
# 测试数据
$str = "3346473664045333504
8346473664045333504
1156703069806098944
8356024549663067136
6522765286266804224
8356396534591913472
8356396434591913472
1771810587495565440";
$lines = explode("n",$str);
# 取出最短的一行长度
$tmpLineLengths = array();
foreach($lines as $v){
$tmpLineLengths[] = strlen($v);
}
$minSortLength = min($tmpLineLengths);
# 竖向扫描
$prefix = null;
for($i = 0;$i < $minSortLength;$i ){
# 取出第$i位字符串
$first = array();
for($j = 0;$j < count($lines);$j ){
$lines[$j] = trim($lines[$j]);# 单行
# 只取前缀一致的行
if(substr($lines[$j],0,$i) == substr($prefix,0,$i)) $first[] = $lines[$j][$i];
}
if(count($first) != 0){
# 取出出现次数最多的字符并K-V更换
$tmpExchange = array_flip(array_count_values($first));
# 再排序KEY（原来的Value）
krsort($tmpExchange,SORT_NUMERIC);
# 竖向字符出现数必须大于等于2时才记录(这个条件不加会取出整行)
if(array_keys($tmpExchange,max($tmpExchange))[0] >= 2) $prefix .= current($tmpExchange);
}
}
echo $prefix;
?>
