PHP 알고리즘 설계 아이디어: 최대 공통 부분 수열 문제에 대한 효율적인 솔루션을 얻는 방법은 무엇입니까?

PHP 알고리즘 설계 아이디어: 최대 공통 부분 수열 문제에 대한 효율적인 솔루션을 얻는 방법은 무엇입니까?

LCS(Longest Common Subsequence)는 두 문자열에서 가장 긴 동일한 부분 수열을 찾는 문제입니다. 실제 응용 분야에서 LCS는 텍스트 유사성 비교, 버전 제어, DNA 서열 비교 ​​등의 분야에서 널리 사용됩니다. 이 기사에서는 이 문제를 해결하기 위한 효율적인 솔루션을 소개하고 구체적인 코드 예제를 제공합니다.

알고리즘 아이디어:

동적 프로그래밍은 LCS 문제를 해결하는 일반적인 방법입니다. LCS 문제는 최적의 부분 구조 특성을 가지고 있습니다. 즉, 두 수열의 가장 긴 공통 부분 수열은 해당 부분 문제의 가장 긴 공통 부분 수열로 구성될 수 있습니다. 이러한 특성에 따라 동적 프로그래밍 방법을 사용하여 LCS 문제를 해결할 수 있습니다.

구체적인 알고리즘 단계는 다음과 같습니다.

1. 2차원 배열 dpm+1을 만듭니다. 여기서 m과 n은 각각 두 입력 문자열의 길이입니다.

   • dpi는 첫 번째 문자열의 첫 번째 i 문자와 두 번째 문자열의 첫 번째 j 문자 사이의 LCS 길이를 나타냅니다.
2. dp 배열의 첫 번째 행과 열을 0, 즉 dpi=dp0=0으로 초기화합니다.

3. 첫 번째 문자열의 i번째 문자와 두 번째 문자열의 j번째 문자에 대해 두 문자열의 각 문자를 반복합니다.

   • 두 문자가 동일한 경우(예: 첫 번째 문자 i-번째 문자) 문자열의 문자는 두 번째 문자열의 j번째 문자와 동일합니다. 그러면 dpi = dpi-1 + 1입니다.
   • 두 문자가 동일하지 않으면 dpi = max(dpi-1, dpi), 즉 이전 문자와 다음 문자의 LCS 중 더 큰 값이 사용됩니다.
4. 두 문자열을 순회한 후 얻은 dpm은 가장 긴 공통 부분 수열의 길이입니다.
5. dp 배열의 결과에 따라 역추적을 통해 가장 긴 공통 부분 수열을 얻을 수 있습니다. dpm부터 왼쪽 상단으로 이동합니다. dpi가 dpi-1 + 1이면 현재 문자가 LCS에 속한다는 의미입니다. 결과 시퀀스에 문자를 추가하고 왼쪽 상단으로 이동합니다.

코드 예:

functionlongestCommonSubsequence($str1, $str2){

$m = strlen($str1);
$n = strlen($str2);
$dp = array();

for($i=0; $i<=$m; $i++){
    $dp[$i] = array_fill(0, $n+1, 0);
}

for($i=1; $i<=$m; $i++){
    for($j=1; $j<=$n; $j++){
        if($str1[$i-1] == $str2[$j-1]){
            $dp[$i][$j] = $dp[$i-1][$j-1] + 1;
        }
        else{
            $dp[$i][$j] = max($dp[$i-1][$j], $dp[$i][$j-1]);
        }
    }
}

$lcs = "";
$i = $m;
$j = $n;

while($i>0 && $j>0){
    if($str1[$i-1] == $str2[$j-1]){
        $lcs = $str1[$i-1] . $lcs;
        $i--;
        $j--;
    }
    else if($dp[$i-1][$j] > $dp[$i][$j-1]){
        $i--;
    }
    else{
        $j--;
    }
}

return $lcs;

}

$str1 = "ABCBDAB";
$str2 = "BDCAB";
$lcs = LongCommonSubsequence( $str1, $str2);
echo "입력 문자열: $str1 및 $str2
";
echo "가장 긴 공통 하위 시퀀스는 $lcs
";
?>

The 위 코드는 다음을 출력합니다:

입력 문자열: ABCBDAB 및 BDCAB
가장 긴 공통 부분 수열: BCBA

결론:

이 기사에서는 동적 프로그래밍 알고리즘을 사용하여 최대 공통 부분 수열 문제를 해결하는 아이디어와 특정 PHP 코드를 소개합니다. 동적 프로그래밍을 사용하면 LCS 문제를 효율적으로 해결할 수 있습니다. 이 알고리즘의 시간 복잡도는 O(m*n)입니다. 여기서 m과 n은 각각 두 입력 문자열의 길이입니다. 실제 응용에서는 롤링 어레이와 같은 기술을 사용하여 공간 복잡성을 줄이는 등 필요에 따라 알고리즘을 최적화할 수 있습니다.

위 내용은 PHP 알고리즘 설계 아이디어: 최대 공통 부분 수열 문제에 대한 효율적인 솔루션을 얻는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!