PHP에서 가장 긴 공통 부분 문자열 알고리즘의 구현 원리

PHP에서 가장 긴 공통 부분 문자열 알고리즘의 구현 원리

가장 긴 공통 부분 문자열(Longest Common Substring)은 두 문자열에서 가장 길고 동일한 연속 부분 문자열을 찾는 데 사용되는 일반적으로 사용되는 문자열 일치 알고리즘입니다. PHP에서는 동적 프로그래밍 알고리즘을 사용하여 가장 긴 공통 부분 문자열을 찾을 수 있습니다.

아래에서는 PHP에서 가장 긴 공통 부분 문자열 알고리즘의 구현 원리를 자세히 소개하고 관련 코드 예제를 첨부하겠습니다.

1. 동적 프로그래밍 알고리즘의 원리

동적 프로그래밍 알고리즘은 하위 문제가 중첩되고 최적의 하위 구조 속성이 있는 문제를 해결하는 데 사용됩니다. 가장 긴 공통 부분 문자열 문제는 이러한 조건을 만족하므로 동적 프로그래밍 알고리즘을 사용하여 풀 수 있습니다.

가장 긴 공통 부분 문자열 문제는 다음과 같이 공식화될 수 있습니다. 두 문자열 S1과 S2가 주어지면 가장 긴 공통 부분 문자열 LCS를 찾습니다.

동적 프로그래밍 알고리즘의 핵심 아이디어는 문제를 여러 하위 문제로 나누고, 하위 문제의 최적해를 해결하여 원래 문제에 대한 최적해를 찾는 것입니다. 가장 긴 공통 부분 문자열 문제의 경우 이를 더 작은 하위 문제로 나눌 수 있습니다. 문자열 S1의 첫 번째 i 문자와 문자열 S2의 첫 j 문자에 대해 S1[i]와 S2[j]가 동일한지 여부를 확인할 수 있습니다. 즉, 새로운 하위 문제를 얻을 수 있습니다. S1의 문제를 해결합니다. S2의 첫 번째 i-1 문자와 첫 번째 j-1 문자의 가장 긴 공통 부분 문자열입니다. 같지 않으면 가장 긴 공통 부분 문자열의 길이는 0입니다.

위의 분할 과정을 통해 동적 프로그래밍 솔루션을 위한 2차원 테이블을 구성할 수 있습니다. 테이블의 행은 S1의 문자를 나타내고, 열은 S2의 문자를 나타내며, 각 셀은 S1의 처음 i 문자와 S2의 처음 j 문자의 가장 긴 공통 부분 문자열의 길이를 나타냅니다. 마지막으로, 테이블의 오른쪽 하단에 있는 셀은 검색된 가장 긴 공통 부분 문자열의 길이입니다.

2. 가장 긴 공통 부분 문자열 알고리즘 구현

아래에서는 PHP에서 가장 긴 공통 부분 문자열 알고리즘의 코드 구현을 제공합니다.

function longestCommonSubstring($str1, $str2) {
    $length1 = strlen($str1);
    $length2 = strlen($str2);

    // 初始化二维数组
    $dp = array();
    for ($i = 0; $i <= $length1; $i++) {
        $dp[$i] = array();
        for ($j = 0; $j <= $length2; $j++) {
            $dp[$i][$j] = 0;
        }
    }

    $maxLen = 0;
    $endIndex = 0;

    // 动态规划求解
    for ($i = 1; $i <= $length1; $i++) {
        for ($j = 1; $j <= $length2; $j++) {
            if ($str1[$i - 1] == $str2[$j - 1]) {
                $dp[$i][$j] = $dp[$i - 1][$j - 1] + 1;
                if ($dp[$i][$j] > $maxLen) {
                    $maxLen = $dp[$i][$j];
                    $endIndex = $i - 1;
                }
            }
        }
    }

    // 根据最长公共子串的长度和结束索引截取子串
    $longestSubstring = substr($str1, $endIndex - $maxLen + 1, $maxLen);

    return $longestSubstring;
}

// 示例
$str1 = "ABCABC";
$str2 = "BABCAB";

$result = longestCommonSubstring($str1, $str2);
echo "最长公共子串：".$result;

위 코드에서 먼저 문자열 S1과 S2의 길이를 계산하고 A로 초기화합니다. 2차원 배열 $dp는 동적 프로그래밍의 결과를 저장하는 데 사용됩니다. 그런 다음 이중 루프를 통해 S1과 S2를 반복하고 현재 문자가 동일한지 여부에 따라 $dp 배열의 값을 업데이트합니다.

마지막으로 가장 긴 공통 부분 문자열의 길이와 끝 인덱스에 따라 substr 함수를 사용하여 가장 긴 공통 부분 문자열을 가로채서 반환합니다.

3. 요약

가장 긴 공통 부분 문자열 알고리즘은 두 문자열에서 가장 길고 동일한 연속 부분 문자열을 찾는 데 사용되는 일반적으로 사용되는 문자열 일치 알고리즘입니다. PHP에서는 동적 프로그래밍 알고리즘을 사용하여 가장 긴 공통 부분 문자열을 찾을 수 있습니다. 동적 프로그래밍 솔루션을 위한 2차원 테이블을 구성함으로써 가장 긴 공통 부분 문자열을 효율적으로 찾을 수 있습니다.

이 글에 소개된 원리와 코드 예제를 통해 독자들은 PHP에서 가장 긴 공통 하위 문자열 알고리즘의 구현에 대해 더 깊은 이해를 갖게 될 것이라고 믿습니다. 이 기사가 독자들이 문자열 일치 문제를 해결할 때 도움이 되기를 바랍니다.

위 내용은 PHP에서 가장 긴 공통 부분 문자열 알고리즘의 구현 원리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!