Get Longest Repeated Sub String

getLongestRepeatedSubStrings.php

<?php

function getLongestRepeatedString($array, $prevStartIndex = 0, $prevEndIndex = 0, $repeatOf = 2, $longestMatchFound = 0, $longestRepeatString = '') {
	$matchCount = 0;
	$startIndex; 
	$endIndex = $prevEndIndex ?: $repeatOf - 1;
	$consecutiveMatchCount = 0;
	$prevLongestRepeatString = $longestRepeatString;
	if ($longestRepeatString) $longestRepeatString .= ', ';
	// var_dump("=========================");
	for ($i = 0; $i < $repeatOf; $i++) {
		$startIndex = $i + $prevStartIndex;
		$startChar = $array[$startIndex];
		$endChar = $array[$endIndex];
		$isMatchingChar = $startChar === $endChar;
		// var_dump("is $startChar (index: $startIndex) === $endChar (index: $endIndex) : " . ($isMatchingChar ? 'true' : 'false'));
		if ($isMatchingChar) {
			$longestRepeatString .= $startChar;
			$consecutiveMatchCount++;
		}
		$endIndex++;
	}
	if ($consecutiveMatchCount !== $repeatOf) $longestRepeatString = $prevLongestRepeatString;
	$nextEndIndex = $prevEndIndex + 1;
	$nextStartIndex = $prevStartIndex + 1;
	$lastIndex = sizeof($array) - 1;
	$lastEndIndexChecked = $endIndex - 1;
	$isLastEndIndexCheck = $lastEndIndexChecked === $lastIndex;
	$isLastStartIndexCheck = $prevStartIndex + 2 * $repeatOf - 2 === $lastIndex;

	// var_dump("lastStartIndexChecked : $startIndex nextStartIndex : $nextStartIndex prevEndIndex : $prevEndIndex prevStartIndex : $prevStartIndex nextEndIndex : $nextEndIndex lastEndIndexChecked: $lastEndIndexChecked lastIndex: $lastIndex repeatOf: $repeatOf longestRepeatString: $longestRepeatString");

	if ($consecutiveMatchCount === $repeatOf) {
		if ($isLastEndIndexCheck && $isLastStartIndexCheck) {
			return $longestRepeatString;
		}
		return getLongestRepeatedString($array, $nextStartIndex, $nextStartIndex + $repeatOf - 1, $repeatOf, $consecutiveMatchCount, $longestRepeatString);
	}

	// if ($nextEndIndex > $lastIndex) die;

	if ($isLastStartIndexCheck) {
		$lowerRepeatCheck = $repeatOf - 1;
		if ($lowerRepeatCheck < $longestMatchFound || $lowerRepeatCheck === 1 || $lowerRepeatCheck < $longestMatchFound) {
			return $longestRepeatString;
		}
		return getLongestRepeatedString($array, 0, 0, $lowerRepeatCheck, $longestMatchFound, $longestRepeatString);
	}

	if ($isLastEndIndexCheck) {
		return getLongestRepeatedString($array, $nextStartIndex, $prevEndIndex, $repeatOf, $longestMatchFound, $longestRepeatString);
	}
	
	return getLongestRepeatedString($array, $prevStartIndex, $nextEndIndex, $repeatOf, $longestMatchFound, $longestRepeatString);
}

function getLongestSubStrings($str) {
	$array = str_split($str);
	$lettersCount = count($array);
	$lastIndex = sizeof($array) - 1;
	$noRepeatitiveSubStringFoundMsg = 'No repeated substring';
	$longestRepeatedSubStrPossible = (int)round($lettersCount / 2);
	// var_dump("str: $str, longestRepeatedSubStrPossible : $longestRepeatedSubStrPossible, lastIndex: $lastIndex");
	$longestSubstringsFound = getLongestRepeatedString($array, 0, 0, $longestRepeatedSubStrPossible);

	$output = $longestSubstringsFound ?: $noRepeatitiveSubStringFoundMsg;

	return "Longest Repeated Substring in $str is: $output";
}
// echo getLongestSubStrings('ABCDEFG'); // Longest Repeated Substring in ABCDEFG is: No repeated substring
// echo getLongestSubStrings('banana'); // Longest Repeated Substring in banana is: ana
// echo getLongestSubStrings('mom'); // Longest Repeated Substring in banana is: ana
// echo getLongestSubStrings('bananaklitban'); // Longest Repeated Substring in banana is: ana, ban
echo getLongestSubStrings('abcpqrabpqpq'); // Longest Repeated Substring in abcpqrabpqpq are: ab, pq