longest common sequence

longestCommonSequence.php

<?php
function longestCommonSequence($str_a, $str_b)
{
    assert("is_string('$str_a')");
    assert("is_string('$str_b')");
    
    $str_a_len = strlen($str_a);
    $str_b_len = strlen($str_b);
    
    $opt = array_fill(0, $str_a_len + 1, array_fill(0, $str_b_len + 1, 0));
    
    for ($i = $str_a_len - 1; $i >=0; $i--) {
        for ($j = $str_b_len - 1; $j >= 0; $j--) {
            if ($str_a[$i] == $str_b[$j]) {
                $opt[$i][$j] = $opt[$i + 1][$j + 1] + 1;
            } else {
                $opt[$i][$j] = max($opt[$i + 1][$j], $opt[$i][$j + 1]);
            }
        }
    }
    
    
    $i = $j = 0;
    
    while($i < $str_a_len && $i < $str_b_len) {
        if ($str_a[$i] == $str_b[$j]) {
            echo $str_a[$i];
        } elseif ($opt[$i + 1][$j] >= $opt[$i][$j + 1]) {
            $i++;
        } else {
            $j++;
        }
    }
}