需要做一個(gè)題目相似度搜索功能，輸入的字符串完全用字符串完全匹配算法進(jìn)行匹配囊榜，考慮使用動態(tài)規(guī)劃實(shí)現(xiàn)审胸，因?yàn)閯討B(tài)規(guī)劃算法中$dp數(shù)組記錄了所有的匹配狀態(tài)，在進(jìn)行運(yùn)算完成以后就可以遍歷$dp卸勺，對輸入字符串的每個(gè)子串都進(jìn)行匹配砂沛。

//拆分字符串
function mbStringToArray($string, $encoding = 'UTF-8') {
    $arrayResult = array();

    while ($iLen = mb_strlen($string, $encoding)) {
        array_push($arrayResult, mb_substr($string, 0, 1, $encoding));
        $string = mb_substr($string, 1, $iLen, $encoding);
    }
    return $arrayResult;
}

//str1是輸入,str2是數(shù)據(jù)庫里面的數(shù)據(jù)
function LCS_cn($str1, $str2, $encoding = 'UTF-8') {
    $mb_len1 = mb_strlen($str1, $encoding);
    $mb_len2 = mb_strlen($str2, $encoding);
    $mb_str1 = mbStringToArray($str1, $encoding);
    $mb_str2 = mbStringToArray($str2, $encoding);
    $len = $mb_len1 > $mb_len2 ? $mb_len1 : $mb_len2;
    $dp = array();
    for ($i = 0; $i <= $len; $i++) {
        $dp[$i] = array();
        $dp[$i][0] = 0;
        $dp[0][$i] = 0;
    }
    $max = 0;
    $new_text = "";
    for ($i = 1; $i <= $mb_len1+1; $i++) {
        for ($j = 1; $j <= $mb_len2+1; $j++) {
            if ($mb_str1[$i - 1] == $mb_str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                if ($dp[$i][$j] > $max) {
                    $max = $dp[$i][$j];
                }
            } else {
                $dp[$i][$j] = 0;
            }
        }
    }
    $ranges = [];
    $last_m = 0;
    for ($k = 0;$k <$mb_len1;$k++) {
        for ($m = $last_m;$m < $mb_len2;$m++) {
            $row = $k;
            $col = $m;
            while ($dp[$row][$col] >0 && (($row<$mb_len1 && $col < $mb_len2) && $dp[$row+1][$col+1]>0)){
                $dp[$row][$col] = 0;
                $row++;
                $col++;
            }
            if ($dp[$row][$col]>2){
                $ranges[] = ['start' => $col - $dp[$row][$col], 'end' => $col];
                $dp[$row][$col] = 0;
            }
        }
    }
   //合并區(qū)間
    usort($ranges,"sortRange");
    for ($i = 0;$i< count($ranges)-1;$i++) {
        for ($j = $i+1;$j<count($ranges);$j++){
            $left = 0;
            $right = 0;
            if ($ranges[$j]['start'] == 0 &&$ranges[$j]['end'] == 0){
                continue;
            }
            if ($ranges[$j]['start'] <= $ranges[$i]['end']){
                $left = 1; // 左邊界合并
            }
            if ($ranges[$j]['end'] <=$ranges[$i]['end']){
                $right = 1;
            }

            if ($left == 1) {
                if ($right == 0) {
                    $ranges[$i]['end'] = $ranges[$j]['end'];
                }
                $ranges[$j]['start'] = 0;
                $ranges[$j]['end'] = 0;
            }
        }
    }
    $start = 0;
    $range_length = 0;
    foreach ($ranges as $value){
        if (!($value['start'] == 0 && $value['end'] == 0 )){
            $range_length += $value['end'] - $value['start']+1;
            $new_text .= mb_substr($str2,$start,$value['start']-$start);
            $text = mb_substr($str2,$value['start'],$value['end']-$value['start']);
            $new_text .= '<font style="color:red">'.$text.'</font>';
            $start = $value['end'];
        }
    }
    $new_text .= mb_substr($str2, $start);
    //計(jì)算匹配率
    $no_latex = strip_tags($str2);
    $no_latex = preg_replace('# #','',$no_latex);
    $no_latex = preg_replace('#（\d{1,2}）#','',$no_latex);
    $no_latex = preg_replace('#；|\.|曙求。|,#','',$no_latex);
    return [1.0* $range_length/mb_strlen($no_latex),$new_text];

}

function sortRange($one,$two){
    return $one['start'] > $two['start'] ? 1:-1;
}

$value =  LCS_cn('偶函數(shù)的：','兩個(gè)偶函數(shù)的乘積是偶函數(shù)碍庵，兩個(gè)奇函數(shù)的乘積是偶函數(shù)映企，偶函數(shù)與奇函數(shù)的乘積是奇函數(shù)');
echo $value[1];

image.png

$value =  LCS_cn('兩個(gè)偶函數(shù)的乘積是偶函數(shù)','兩個(gè)偶函數(shù)的乘積是偶函數(shù)，兩個(gè)奇函數(shù)的乘積是偶函數(shù)静浴，偶函數(shù)與奇函數(shù)的乘積是奇函數(shù)');

image.png