Skip to content

Instantly share code, notes, and snippets.

@adhocore
Created December 18, 2013 15:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save adhocore/8024324 to your computer and use it in GitHub Desktop.
Save adhocore/8024324 to your computer and use it in GitHub Desktop.
max length of border having atleast three non-overlapping occurance in a string
<?php
/**
* For a given string S, a substring b is said to be its border if S starts and end with b.
* Suppose we need length of longest border b that also occurs in S, even after b is trimmed at ends of S.
*
* This function is aimed at that need. ;)
*
*/
function maxBorderLen($S){
$m = 0;
$l = (int) strlen($S) / 2;
for ($i = 1; $i < $l; $i++) {
if ($b = substr($S, 0, $i) and $b == substr($S, 0-$i)
and substr_count($S, $b) > 2 // the border has to be atleast three non-overlapping occurance
) {
$m = $i;
}
}
return $m;
}
// Tests:
echo maxBorderLen('abczabczabc'); // 3
echo maxBorderLen('abczbcazabcab'); // 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment