diff.php

<?php

// get all sub strings for a given string
// return an array whose count is O(n^2)
function all_substr($str)
{
    $length = strlen($str);
    $ret = array();
    for ($i=0; $i < $length; $i++) {
        $max_length = $length - $i;
        for ($j=1; $j <= $max_length; $j++) {
            $ret[] = substr($str, $i, $j);
        }
    }
    return $ret;
}

// get all common sub strings for two given string
// O(n^4)
function common_subs($a, $b)
{
    $ret = array();
    $as = all_substr($a);
    foreach ($as as $s) { // O(n^2)
        $pos = strpos($b, $s); // O(m*n)
        if ($pos !== false) {
            $ret[] = $s;
        }
    }
    return $ret;
}

// great common sub string
function gcs($a, $b)
{
    $all = common_subs($a, $b);
    $max_len = 0;
    $g = '';
    foreach ($all as $s) {
        $len = strlen($s);
        if ($len > $max_len) {
            $max_len = $len;
            $g = $s;
        }
    }
    return $g;
}

function diff($a, $b)
{
    $cs = gcs($a, $b);
    if (empty($cs)) {
        return array(
            '-' => $a,
            '+' => $b,
        );
    }
    $cslen = strlen($cs);
    $ap = strpos($a, $cs);
    $bp = strpos($b, $cs);
    $la = substr($a, 0, $ap);
    $lb = substr($b, 0, $bp);
    $ra = substr($a, $ap+$cslen);
    $rb = substr($b, $bp+$cslen);
    return array(diff($la, $lb), $cs, diff($ra, $rb));
}

$a = 'add';
$b = 'dad';
$diff = diff($a, $b);
print_r($diff);