Longest Repeated Substring

Longest repeated substring is an algorithm that finds the longest substring of a string that occurs at least twice.

									function LongestRepeatedSubstring($str)
{
	if ($str == null)
		return null;

	$N = strlen($str);
	$substrings = array();

	for ($i = 0; $i < $N; $i++)
	{
		$substrings[$i] = substr($str, $i);
	}

	sort($substrings);

	$result = "";

	for ($i = 0; $i < $N - 1; $i++)
	{
		$lcs = LongestCommonString($substrings[$i], $substrings[$i + 1]);

		if (strlen($lcs) > strlen($result))
		{
			$result = $lcs;
		}
	}

	return $result;
}

function LongestCommonString($a, $b)
{
	$n = min(strlen($a), strlen($b));
	$result = "";

	for ($i = 0; $i < $n; $i++)
	{
		if ($a[$i] == $b[$i])
			$result = $result . $a[$i];
		else
			break;
	}

	return $result;
}

Example

									$data = "the quick brown fox jumps over the lazy dog";
$value = LongestRepeatedSubstring($data);

Output

the