PHP에서 가장 긴 공통 부분 문자열을 찾는 방법

이 글에서는 주로 PHP에서 가장 긴 공통 부분 문자열 문제를 해결하는 방법을 소개하고, 가장 긴 공통 부분 문자열 문제를 해결하는 알고리즘 원리를 간략하게 설명하고, PHP에서 가장 긴 공통 부분 문자열 문제를 해결하는 구체적인 운영 기법을 예제 형식으로 분석합니다. , 도움이 필요한 친구가 참고할 수 있습니다

자세한 내용은 다음과 같습니다.

질문: 문자열 1의 모든 문자가 문자열에 표시된 순서대로 다른 문자열 2에 나타나는 경우 문자열 1을 a라고 합니다. 문자 문자열 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:suwjwwakzzhghbsmnksg
LCS:absm
Totle time is 0.000648975372314 s

관련 권장 사항:

JavaScript에서 가장 큰 공통 부분 문자열을 찾는 방법에 대한 자세한 설명

상세 설명 PHP를 사용하여 두 문자열 중 가장 긴 공통 부분 문자열을 찾습니다

PHP는 가장 긴 공통 부분 문자열을 찾는 아이디어를 구현합니다

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