PHP는 가장 긴 공통 부분 문자열을 해결하는 방법을 실현합니다.

이 기사의 예에서는 PHP에서 가장 긴 공통 부분 문자열 문제를 해결하는 방법을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 자세한 내용은 다음과 같습니다.

제목: 문자열 1의 모든 문자가 문자열에 나타나는 순서대로 다른 문자열 2에 나타나면 문자열 1을 문자열 2의 하위 문자열이라고 합니다.

하위 문자열(문자열 1)의 문자가 문자열 2에 연속적으로 나타나야 하는 것은 아닙니다. 즉, 불연속적일 수는 있지만 순서는 변경할 수 없습니다.

두 개의 문자열을 입력하고, 가장 긴 공통 부분 문자열을 찾아, 가장 긴 공통 부분 문자열을 출력하는 함수를 작성하세요.

예를 들어, 두 개의 문자열 BDCABA 및 ABCBDAB를 입력하면 문자열 BCBA 및 BDAB는 가장 긴 공통 하위 문자열인

입니다. 다음 알고리즘은 인터넷의 Java 알고리즘을 기반으로 Jiu Xiaoyao가 번역했습니다

이미 수정됨

LCS 클래식 알고리즘 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();
?>

실행 결과:

substring1:cgqtdaacneftabsxvmlb
substring2:suwjwakzzhghbsmnksg
LCS:absm
총 시간은 0.000648975372314초

관련 권장 사항: Java Script 사용자 정의 함수는 두 문자열 중 가장 긴 공통 부분 문자열을 찾는 방법을 구현합니다

Python의 가장 긴 공통 부분 문자열 알고리즘 예제

PHP를 사용하여 가장 긴 공통 부분 문자열 문제를 해결하세요

위 내용은 PHP는 가장 긴 공통 부분 문자열을 해결하는 방법을 실현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!