check out my new blog at gmarik.info/blog

Friday, April 29, 2005

Longest Common Sequence

Ok, i've been striving for few hours to get this working...
It searches Longest Common Sequence within 2 ordered sets.
So here's the code:


<?php

/*
*
* @Algorithm : LongestCommonSequence
* @Author : mrix
* @Date : 28.04.2005
* @Ver : 1.1
*/

function searchLCS($big,$small){

if (0 == strlen($big) || 0 == strlen($small))
return '';

$resultl = $resultr = '';

if ( false !== strchr($big,$small{0}))
$resultl = $small{0}.searchLCS(
substr($big,strpos($big,$small{0})+ 1),
substr($small,1));

$resultr = searchLCS($big,substr($small,1));
return ((strlen($resultl) > strlen($resultr)) ? $resultl:$resultr);
}
echo searchLCS("cocacola","cosdfla");
# yelds : cola

?>


0 Comments:

Post a Comment

<< Home