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

Popular posts from this blog

PHP function for checking IMEI

Luhn algorithm for IMEI Check public function __checkIMEI($imei){ if(strlen($imei)==15){ $imeia=($imei[1]*2); if(strlen($imeia)==2){$imeia=str_split($imeia,1); $imeia=$imeia[0]+$imeia[1]; } $imeib=($imei[3]*2); if(strlen($imeib)==2){$imeib=str_split($imeib,1); $imeib=$imeib[0]+$imeib[1]; } $imeic=($imei[5]*2); if(strlen($imeic)==2){$imeic=str_split($imeic,1); $imeic=$imeic[0]+$imeic[1]; } $imeid=($imei[7]*2); if(strlen($imeid)==2){$imeid=str_split($imeid,1); $imeid=$imeid[0]+$imeid[1];} $imeie=($imei[9]*2); if(strlen($imeie)==2){$imeie=str_split($imeie,1); $imeie=$imeie[0]+$imeie[1]; } $imeif=($imei[11]*2); if(strlen($imeif)==2){$imeif=str_split($imeif,1); $imeif=$imeif[0]+$imeif[1]; } $imeig=($imei[13]*2); if(strlen($imeig)==2){$imeig=str_split($imeig,1); $imeig=$imeig[0]+$imeig[1]; } $IMEI= ($ime...

PHP code for finding distinct elements common to all rows of a matrix in O(n) time complexity

<?php class Matrix{ /** •@param 2D array $matrix • •Prints distinct elements common to all rows of the matrix */ public static function getDistinctElementsCommonToAllRows($matrix){ // A hash map to store count of elements $hashmap = array(); $selectedHash = array(); $rows = count($matrix); $cols = count($matrix[0]); for ($i = 0; $i < $rows; $i++) { // Increment the count of first // element of the row if(array_key_exists($matrix[$i][0],$hashmap)){ $hashmap[$matrix[$i][0]] = $i+1; } // Starting from the second element // of the current row for ($j = 1; $j < $cols; $j++) { ...

Magic Function in PHP (__sleep() and __wakeup() )

There are many magic methods in PHP like  __construct(), __destruct(), __callback(), __get(), __set(), __sleep(), __wake() and many more. But we will be takingon  on  __sleep() and  __wake(). __sleep() : serialize() checks if your class has a function with the magic name __sleep(). If so, that function is executed prior to any serialization. It can clean up the object and is supposed to return an array with the names of all variables of that object that should be serialized. If the method doesn't return anything then NULL is serialized and E_NOTICE is issued. serialize() is used for the representation of the storage class for storing the value. Serializing   an object means converting it to a byte stream representation that can be stored in a file. The use of __sleep()  to commit the pending task. If a bulk data is being inserted then at that time __sleep can be used. it will not release the object unless the work is not completed....