欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  php教程

用PHP求解最长公共子串问题

程序员文章站 2022-04-10 12:24:24
...
用PHP求解最长公共子串问题
<?php
class LCS{
	public static function main(){
		//设置字符串长度  
        $substringLength1 = 20;  
        $substringLength2 = 20;  //具体大小可自行设置 
        $opt=array_fill(0,21,array_fill(0,21,null));  
		
		// 随机生成字符串  
        $x = self::GetRandomStrings($substringLength1);  
        $y = self::GetRandomStrings($substringLength2);  
   		
		$startTime = microtime(true);

		// 动态规划计算所有子问题  
        for ($i = $substringLength1 - 1; $i >= 0; $i--){  
            for ($j = $substringLength2 - 1; $j >= 0; $j--){  
                if ($x[$i] == $y[$j])  
                    $opt[$i][$j] = $opt[$i + 1][$j + 1] + 1;          
                else  
                    $opt[$i][$j] = max($opt[$i + 1][$j], $opt[$i][$j + 1]);      
            }  
        } 

		echo "substring1:".$x."\r\n";  
		echo "substring2:".$y."\r\n";  
		echo "LCS:";  


		$i = 0;
		$j = 0;  
        while ($i < $substringLength1 && $j < $substringLength2){  
            if ($x[$i] == $y[$j]){  
                echo $x[$i];  
                $i++;  
                $j++;  
            } else if ($opt[$i + 1][$j] >= $opt[$i][$j + 1])  
                $i++;  
            else  
                $j++;  
        }  

		$endTime = microtime(true);

		echo "\r\n";
        echo "Totle time is " . ($endTime - $startTime) . " s";  
	}

	public static function GetRandomStrings($length){
		$buffer = "abcdefghijklmnopqrstuvwxyz";
		$str="";
		for($i=0;$i<$length;$i++){
			$random=rand(0,strlen($buffer)-1); 
			$str.=$buffer[$random];
		}
		return $str;
	}
}



LCS::main();
?>

以上就是用PHP求解最长公共子串问题的内容,更多相关内容请关注PHP中文网(www.php.cn)!

相关标签: PHP,公共子串