最长公共前缀

零式的天空

发布于 2022-03-21 20:57:42

3060

发布于 2022-03-21 20:57:42

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

实现一：竖向扫描

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