Skip to main content

PHP code for finding Longest Repeated Substrings (LRS)

<?php

Class LRS{

/**

•@param array $texts

•Prints longest repeated substrings for each text */

        public static function getAllLRS($texts){
                $stringArr = array();
                foreach($texts as $string){
                        $stringArr[] = self::LongestRepeatedSubstring($string);
                }
                return $stringArr;
        }

        public function LongestRepeatedSubstring($string){
                if ($string == null)
                        return null;

                $string_length = strlen($string);
                $substrings = array();
                
                for ($i=0; $i < $string_length; $i++){
                        $substrings[$i] = substr($string, $i);
                }

                sort($substrings);

                $result = "";

                for ($i = 0; $i < $string_length - 1; $i++){
                        $lcs = self::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));
                $lcs_result = "";
                for ($i = 0; $i < $n; $i++){
                        if ($a[$i] == $b[$i]){
                                $lcs_result = $lcs_result.$a[$i];
                        }else{
                                break;
                        }        
                }
                return $lcs_result;
        }
}

print_r(LRS::getAllLRS(['ABCDEFG','banana','abcpqrabpqpq']));
?>

Comments