PHP 最长公共子序列LCS 中文汉字版本怎么写?

已经写了ASCII字母版

function LCS($str_1, $str_2) {
  $len_1 = strlen($str_1);
  $len_2 = strlen($str_2);
  $len = $len_1 > $len_2 ? $len_1 : $len_2;

  $dp = array();
  for ($i = 0; $i <= $len; $i++) {
    $dp[$i] = array();
    $dp[$i][0] = 0;
    $dp[0][$i] = 0;
  }

  for ($i = 1; $i <= $len_1; $i++) {
    for ($j = 1; $j <= $len_2; $j++) {
      if ($str_1[$i - 1] == $str_2[$j - 1]) {
        $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
      } else {
        $dp[$i][$j] = $dp[$i - 1][$j] > $dp[$i][$j - 1] ? $dp[$i - 1][$j] : $dp[$i][$j - 1];
      }
    }
  }

  return $dp[$len_1][$len_2];
}

如何扩展成中文版?

我自己解决了,只能自问自答了

<?php
//最长公共子序列英文版
function LCS_en($str_1, $str_2) {
  $len_1 = strlen($str_1);
  $len_2 = strlen($str_2);
  $len = $len_1 > $len_2 ? $len_1 : $len_2;

  $dp = array();
  for ($i = 0; $i <= $len; $i++) {
    $dp[$i] = array();
    $dp[$i][0] = 0;
    $dp[0][$i] = 0;
  }

  for ($i = 1; $i <= $len_1; $i++) {
    for ($j = 1; $j <= $len_2; $j++) {
      if ($str_1[$i - 1] == $str_2[$j - 1]) {
        $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
      } else {
        $dp[$i][$j] = $dp[$i - 1][$j] > $dp[$i][$j - 1] ? $dp[$i - 1][$j] : $dp[$i][$j - 1];
      }
    }
  }

  return $dp[$len_1][$len_2];
}

//拆分字符串
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;
}

//最长公共子序列中文版
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;
  }

  for ($i = 1; $i <= $mb_len1; $i++) {
    for ($j = 1; $j <= $mb_len2; $j++) {
      if ($mb_str1[$i - 1] == $mb_str2[$j - 1]) {
        $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
      } else {
        $dp[$i][$j] = $dp[$i - 1][$j] > $dp[$i][$j - 1] ? $dp[$i - 1][$j] : $dp[$i][$j - 1];
      }
    }
  }

  return $dp[$mb_len1][$mb_len2];
}
  • 怎么能通俗易通的了解php中的反射和依赖注入这两个概念
  • mysql中查询条件的先后顺序问题?
  • 微信接入验证代码中,<?php?>是什么意思?
  • PHP NULL的问题
  • laravel新手获取单行数据问题
  • 非phpfpm模式如何先echo响应再继续执行
  • GitHub上的php的Psr规范的文档找不到了
  • PHP按某月统计每个小时生成的数据
  • 用zend studio+xdebug单步调试php
  • thinkphp中上传文件应该单独提交该是和所有其他Input一起提交?
  • symfony2 表单和entity疑问