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

이번에는 PHP에서 가장 긴 공통 부분 문자열을 찾는 방법을 보여 드리겠습니다. 가장 긴 공통 부분 문자열을 찾는 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:suwjwwakzzhghbsmnksg
LCS:absm
Totle time is 0.000648975372314 s

이 기사의 사례를 읽으신 후 방법을 마스터하셨다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!

추천 자료:

Swoole과 WebSocket을 사용하여 채팅방을 개발하는 방법

PHP에서 난수를 생성하는 방법은 무엇입니까

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