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

Write a function that checks if a given word stored in a doubly linked list is a palindrome.

<?php class Node { public $value; public $next = null; // next node public $prev = null; // previous node public function __construct($value) { $this->value = $value; } } class Palindrome { /** •@param string $word •@return bool */ public static function isPalindrome($head, $tail){ if ($head == null) return true; while ($head != $tail){ if ($head->value != $tail->value) return false; $head = $head->next; $tail = $tail->prev; } return true; } } $head = new Node(1); $firstNode = new Node(2); $secondNode = new Node(3); $tail = new Node(4); $head->next = $firstNode; $firstNode->prev = $head; $firstNode->next = $secondNode;...

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....