David Tavarez’s Home at davidtavarez.com

The longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.

The problem of longest common subsequence arises whenever we search for similarities across multiple texts. A particularly important application is in finding a consensus among DNA sequences. The genes for building particular proteins evolve with time, but the functional regions must remain consistent in order to work correctly. By finding the longest common subsequence of the same gene in different species, we learn what has been conserved over time.

The longest common substring problem is a special case of edit distance, when substitutions are forbidden and only exact character match, insert, and delete are allowable edit operations. Under these conditions, the edit distance between p and t is n+m-2 |lcs(p,t)|, since we can delete the missing characters from p to the lcs(p,t) and insert the missing characters from $t$ to transform p to t. This is particularly interesting because the longest common subsequence can be faster to compute than edit distance.

For More Information about it, just google it!.

The Implementation.

/**
 * Implementación de el Algoritmo "Longer Common SubString" en dos (2) Cadenas dadas.
 *
 * @param string $a
 * @param string $b
 * @return integer
 */
function lcs($a, $b) {
	if (! is_string ( $a ) || ! is_string ( $b ))
		return false;
	$m = strlen ( $a );
	$n = strlen ( $b );
	for($i = 0; $i < $m; $i ++)
		$c [$i] [0] = 0;
	for($j = 0; $j < $n; $j ++)
		$c [0] [$j] = 0;
	for($i = 1; $i <= $m; $i ++) {
		for($j = 1; $j <= $n; $j ++) {
			if ($a [$i] == $b [$j])
				$c [$i] [$j] = $c [$i] [$j - 1] + 1;
			else {
				if ($c [$i - 1] [$j] >= $c [$i] [$j - 1])
					$c [$i] [$j] = $c [$i - 1] [$j];
				else
					$c [$i] [$j] = $c [$i] [$j - 1];
			}
		}
	}
	return $c [$m] [$n];
}

Share on Facebook