Как правильно получить отрицательный результат подстроки?

Question

[Сергей Золотарёв]

Добрый вечер!
Недавно столкнулся с тем, когда после второго теста моего решения задачи на PHP не получил обязательного результата, что должен был сделать это в соответствии с условиями решения задачи.

Суть задачи такова и каковы условия его решения:



Первый тест прошёл успешно в соответствии с условиями решения, а второй тест принёс плохие сюрпризы, давая различные сообщения компилятора:

PHP Notice:  String offset cast occurred in <код решения> on line 45
PHP Notice:  String offset cast occurred in <код решения> on line 46

Код проблемного решения(по которому компилятор вывел сообщения) в комментариях к моему вопросу, чтобы вы могли знать, с чем я к вам обратился и чтобы вы могли мне помочь с этим;-)
Как правильно сделать проверку отрицательности подстрок, чтобы выводился -1, если программа правильно не даёт правильных подстрок?
Заранее вам спасибо!

Comments

[Сергей Золотарёв]

Сам почти полноценный код моего решения на PHP, где нужно избежать одной ошибки:

<?php
function isPalindrome($freq, $k){
    $flag = 0;
    $length = 0;

    for ($i=0; $i < 26; $i++) { 
        if ($freq[$i] == 0){
            continue;
        }
        else if ($freq[$i] == 1){
            $flag = 1;
        }
        else {
            if ($freq[$i] & 1){
                $flag = 1;
            }
            $length += $freq[$i] / 2;
        }
    }
    if ($k & 1) {
        if (2 * $length + $flag >= $k){
            return TRUE;
        }
    }
    else {
        if (2 * $length >= $k){
            return TRUE;
        }
    }

    return FALSE;

}
function Check($strdata, $m, $k){
    $freq = array_fill(0, 26, 0); 

    for ($i = 0; $i < $m; $i++){
        $freq[ord($strdata[$i]) - ord('a')]++; 
    }
    if (isPalindrome($freq, $k)) {
        return TRUE; 
    }

    for ($i = $m; $i < strlen($strdata); $i++){
        $freq[ord($strdata[$i - $m]) - ord('a')] -= 1; 
        $freq[ord($strdata[$i]) - ord('a')] += 1; 

        if (isPalindrome($freq, $k)) {
            return TRUE; 
        }
    } 


    return FALSE;

}
function Find($strdata, $n, $k){
    $l = $k; 
    $h = $n;

    $ans = -1; 

  

    while ($l <= $h) { 

        $m = floor(($l + $h) / 2); 

        if (Check($strdata, $m, $k)){ 
            $ans = $m; 
            $h = $m - 1; 
        } 

        else{
            $l = $m + 1; 
        } 

    }

    return $ans; 
}

fscanf(STDIN, "%s", $str); 
$n = strlen($str);
$k = 2;

if(!Find($str,$n,$k)){
    echo -1;
}

$fstr = substr($str,0,Find($str,$n,$k));

echo $fstr;
?>

Answer 1

[Wataru]

Помимо очевидных проблем, у вас неверная проверка на палиндромность.

Ваш код, например посчитает палиндромом строку "aab".
Потом, тут еще зачем-то бинпоиск присобачен. Зачем, вообще непонятно.
И еще ваше решение слишком медленное. Тут сложность порядка O(n^2 log n), что для 200000 ни в какие ограничения не влезет.

Для правильного решения нужно только одно наблюдение - у любого палиндрома можно взять середину длиной 2 или 3 - это будет более короткий палиндром. Поэтому, если в строке есть хоть какие-то палиндромы, то точно есть палиндромы длины 2 или 3.

решение

Надо проверить, есть ли 2 подряд идущих одинаковых символа. Если есть - лексикографически минимальная такая пара - ответ.
Иначе, надо проверить, есть ли тройка символов, где первый равен третьему. Из всех таких надо выбрать лексикографически минимальную.
Если и таких нет, то ответ "-1".

Задача решается за 2 не вложенных цикла.

Answer 2

[Rsa97]

Здесь вы получаете вещественное значение $m:
$m = floor(($l + $h) / 2);
А здесь пытаетесь использовать вещественное значение в качестве индекса:

$freq[ord($strdata[$i - $m]) - ord('a')] -= 1; 
$freq[ord($strdata[$i]) - ord('a')] += 1;

Используйте intdiv, а не floor:
$m = intdiv(($l + $h), 2);

Comments

[Сергей Золотарёв]

И ещё у меня есть копия решения, написанная на языке Python и питоновский компилятор тоже сообщил о том, что сам floor не существует:
Undefined variable 'floor'

Сам кусок кода, на который ссылается компилятор:
m = floor((l + h) / 2)

Как такой же вариант, которым вы поделились со мной, реализовать на самом Python, понадобие intdiv из PHP?

[Rsa97]

Сергей Золотарёв, // - целочисленное деление в Python