seregazolotaryow64
@seregazolotaryow64
Аутист и веб-разработчик

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

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

Суть задачи такова и каковы условия его решения:
y4mZtJszfaB22i0Z7IqY-HvOSWmuFtzKTNqFeb20QaRyNSBgBa2NQqCthcp3129GR0mmPyJKIKzD3vAks7SZeioDyikyhVDg8RPrbUy_h6AzrDnYnHgLk9McDxuS7JwJWMEliJTPh3P1rS_QRKvdJoIZouva6wTBcRU7wSB-MtK8M24yVEjiFE9O8SHWI3vpcDR9Q0p3T-qQFhmBSLZCW74XQ?width=1800&height=1200&cropmode=none
y4mKLav5aKHE45Pd600FGt36I-WtQnrLza2EsX_ZM4to7WUJipxtZaMNJCDsfrAJyxzHOb_DLe3w0gJqOcXLJvLMhNhR7LGV5GGRAEoGmy5pOcG2oXo8-8pqfUVv794GwqRiDp04u6nQ_UftZ8txxLvtmRybpz_3SQcPO37eHCpOYrtklfthtGpT4SLuqG6A_KmlzbbBNLt0eelCHZTpdu43w?width=1800&height=1200&cropmode=none

Первый тест прошёл успешно в соответствии с условиями решения, а второй тест принёс плохие сюрпризы, давая различные сообщения компилятора:
PHP Notice:  String offset cast occurred in <код решения> on line 45
PHP Notice:  String offset cast occurred in <код решения> on line 46

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

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

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

решение

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

Задача решается за 2 не вложенных цикла.
Ответ написан
Rsa97
@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);
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
RecruitIT Москва
от 100 000 до 160 000 ₽
The ZAL Москва
от 140 000 до 180 000 ₽
от 130 000 до 180 000 ₽
25 окт. 2020, в 17:04
3000 руб./за проект
25 окт. 2020, в 16:59
60000 руб./за проект
25 окт. 2020, в 16:56
30000 руб./за проект