最长公共前缀
Pin Young Lv9

最长公共前缀(Longest Common Prefix): 从多行字符串中找出最长相同的前缀

实现一:竖向扫描

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
<?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;
?>

实现二:纵向扫描

实现三:trie

实现四:…