<?php class LCS { var $str1; var $str2; var $c = array(); /*返回串一和串二的最长公共子序列 */ function getLCS($str1, $str2, $len1 = 0, $len2 = 0) { $this->str1 = $str1; $this->str2 = $str2; if ($len1 == 0) $len1 = strlen($str1); if ($len2 == 0) $len2 = strlen($str2); $this->initC($len1, $len2); return $this->printLCS($this->c, $len1 - 1, $len2 - 1); } /*返回两个串的相似度 */ function getSimilar($str1, $str2) { $len1 = strlen($str1); $len2 = strlen($str2); $len = strlen($this->getLCS($str1, $str2, $len1, $len2)); return $len * 2 / ($len1 + $len2); } function initC($len1, $len2) { for ($i = 0; $i < $len1; $i++) $this->c[$i][0] = 0; for ($j = 0; $j < $len2; $j++) $this->c[0][$j] = 0; for ($i = 1; $i < $len1; $i++) { for ($j = 1; $j < $len2; $j++) { if ($this->str1[$i] == $this->str2[$j]) { $this->c[$i][$j] = $this->c[$i - 1][$j - 1] + 1; } else if ($this->c[$i - 1][$j] >= $this->c[$i][$j - 1]) { $this->c[$i][$j] = $this->c[$i - 1][$j]; } else { $this->c[$i][$j] = $this->c[$i][$j - 1]; } } } } function printLCS($c, $i, $j) { if ($i == 0 || $j == 0) { if ($this->str1[$i] == $this->str2[$j]) return $this->str2[$j]; else return ""; } if ($this->str1[$i] == $this->str2[$j]) { return $this->printLCS($this->c, $i - 1, $j - 1) . $this->str2[$j]; } else if ($this->c[$i - 1][$j] >= $this->c[$i][$j - 1]) { return $this->printLCS($this->c, $i - 1, $j); } else { return $this->printLCS($this->c, $i, $j - 1); } } } /** * 字符串排序 * @description 将答案 ADCB 转换成 ABCD * @param string $string * @param string $sort asc|desc * @return string */ function answerSort($string = '',$sort = 'asc'){ if(empty($string)){ return ''; } //拆分成数组,然后排序 $arr = mb_str_split($string); if($sort == 'asc'){ sort($arr);//值升序 }else{ rsort($arr);//值降序 } //返回新字符串 $string = implode('',$arr); return $string; } /** * 将字符串分割为数组 * @param string $str 字符串[支持中文字符串] * @return array 分割得到的数组 */ function mb_str_split($str) { return preg_split('/(?<!^)(?!$)/u', $str); } $c = answerSort("几天奶奶3天气sa1"); $b = answerSort("气几天13sa"); $lcs = new LCS(); //返回最长公共子序列 echo $lcs->getLCS($c, $b);
标签:return,string,str2,str1,len2,len1,字符串,匹配,php From: https://www.cnblogs.com/zhangtianle/p/17119431.html