Jakiś czas temu obiecałem przedstawić rozwiązanie zadania 15 z konkursu na stronie codecup.pl. Czas dotrzymać słowa, tak więc publikuję moje rozwiązanie i jeśli ktoś ma ochotę, to zapraszam do komentowania, ulepszania, itp. :)

<?php

function code($text, $minLength) {
    $maxLength = strlen($text);
    $result = array(
        'substring' => '',
        'count' => 0,
        'length' => 0,
        'position' => $maxLength + 1
    );
    for ($substringLength = $minLength; $substringLength <= $maxLength; $substringLength++) {
        for ($startPosition = 0; $startPosition <= $maxLength - $substringLength; $startPosition++) {
            $substring = substr($text, $startPosition, $substringLength);
            $count = preg_match_all("/(?=$substring)/", $text, $chunks);
            $replace =
                ($count > $result['count']) ||
                ($count == $result['count'] && $substringLength > $result['length']) ||
                ($count == $result['count'] && $substringLength == $result['length'] && $startPosition < $result['position']);
            if ($replace) {
                $result['substring'] = $substring;
                $result['count'] = $count;
                $result['length'] = $substringLength;
                $result['position'] = $startPosition;
            }
        }
    }
    return $result['substring'];
}
?>

Kluczowym elementem algorytmu jest trik z wyrażeniem w preg_match_all powodującym zliczenie liczby wystąpień podciągu w ciągu z zapewnieniem warunku, że "te same litery mogą być użyte do utworzenia więcej niż jednego ciągu".

Rozwiązanie zadania u Albiego.

Kategorie: Studia i nauka, Techblog, Webdesign Trackback URL