Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY
Текстовый файл (приложен в архиве) состоит не более чем из 1 200 000 символов X, Y, и Z. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY.
Верный ответ: 1713.
Моя программа выдает 1707.
Можно ли поправить мою прогу и какая будет рациональней?
Вложения
| 24-25.zip (226.7 Кб, 8 просмотров) |
Определите максимальное количество идущих подряд пар символов
Дана строка из согласных P, Q, X, Z и гласных E, U букв. Определите максимальное количество идущих.
Определите максимальное количество идущих подряд символов, среди которых нет подстроки XYZ
Текст задачи: Текстовый файл состоит не более чем из 1200000 символов, которые являются прописными.
Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны
Здравствуйте, возникла проблема. К великому сожалению не могу решить задачку, вроде и не сложная, а.
Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны
Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество.
Сообщение от iSmokeJC
YuS_2, кстати, наши решения неправильные
Добавлено через 1 минуту
А у Gdez — правильное
Сообщение от iSmokeJC
не то, чтобы неправильные, т.к. приводят к правильному результату, всё же. но я бы сказал, что мой изначальный вариант, был просто более корявый, а по сути решения, то же самое, только недостающие символы добавляются уже после нахождения наиболее длинной строки, в отличии от решения Gdez.
ЗЫ
Одно но. в решении Gdez, уже полную строку с всеми реальными символами, никак не получить.
YuS_2, а зачем Вам строка в 1200000 символов? Что Вы с ней делать станете? У Вас спросили про длину подстроки, ответ получен. Всё.
А исходную строку изначально можно было скопировать
YuS_2, а решение у Вас неправильное. Вы отняли 2 символа, а лишний символ-то может быть и один.
Сообщение от YuS_2
Сообщение от YuS_2
Сообщение от кот Бегемот
Читать буду, все 1200000 символов.
Сообщение от кот Бегемот
Это у Вас, может быть, "всё". а в реальной жизни, строки режут не только лишь для получения их длины.
Сообщение от кот Бегемот
Зачем копировать исходную строку? А вот чтобы скопировать искомую подстроку, её прежде необходимо определить, путем подсчета длины. как определять будем, что копировать?
Сообщение от iSmokeJC
Ну, в общем-то да, если следовать условиям буквально. но, см. выше, про реальность
Сообщение от кот Бегемот
Сообщение от iSmokeJC
Все-таки для больших строк replace будет не сильно эффективным (и время и память!) Почему не:
Сообщение от кот Бегемот
Сообщение от Catstail
Определите максимальное количество идущих подряд троек символов
Здравствуйте, не могу решить задачу: Текстовый файл 24.txt содержит строку из заглавных.
Определите максимальное количество идущих подряд пар символов
Текстовый файл состоит из символов A, C, D, F и O. Определите максимальное количество идущих.
Определите максимальное количество идущих подряд троек символов
Помогите найти ошибку, выдает 3, а надо 16 Текстовый файл 24-197.txt содержит строку из.
Определите максимальное количество идущих подряд пар символов
(А. Калинин) Текстовый файл 24-215.txt содержит строку из символов A, B, C и цифр 1, 2, 3, всего не.
ЕГЭ задание 24 Определите максимальное количество идущих подряд символов
Текстовый файл 24-157.txt состоит не более чем из 106 символов и содержит только заглавные буквы.
Текстовый файл состоит не более, чем из 1 200 000 прописных символов латинского алфавита. Определите.
Можно решить задачу с помощью алгоритма двух указателей (two pointers). Один указатель будет указывать на начало текущей подстроки, а второй — на текущий символ в тексте. Будем двигать второй указатель по тексту и проверять, что в текущей обрабатываемой подстроке нет подряд идущих символов из набора Q, R, S в различных комбинациях. Если такое условие выполняется, то увеличиваем длину текущей подстроки и продолжаем двигать второй указатель. Если условие не выполняется, то двигаем первый указатель на один символ вправо и продолжаем двигать второй указатель. При этом в каждый момент времени в переменной max будет храниться максимальная длина найденной подстроки без подряд идущих символов из набора Q, R, S в различных комбинациях.
Почему работает неправильно код?
Подскажите пожалуйста, в чём проблема? "Текстовый файл состоит не более чем из 1 200 000 символов X, Y, и Z. Определите максимальное количество идущих подряд символов, среди которых нет подстроки XZZY" Файл не могу загрузить.
Но выдаётся неправильный ответ
То что происходит в функции max_proper_substr лучше всего нарисовать:
Точками обозначены последовательности символов в которых нет комбинации XYYZ .
Подстроки свободные от XZZY обозначены пунктирными линиями. Как видите они перекрываются. Код ниже учитывает это:
Читать файл тоже надо умеючи. В хвосте файла, скорее всего будет перевод строки, который надо убрать вызовом strip . Иначе он может быть зачтён в длину последней подстроки.
Код выше правильно решает поставленную задачу при любых входных данных. То что в ЕГЭ только один тест и строка в середине позволяет срезать угол. Я срезать угол не стану, а покажу ещё одно правильное полное решение. Идея в том чтобы разбить текст на фрагменты, а затем увеличить длину фрагментов на шесть, если они внутри, и на три, если с краю. Код правильно сработает даже если фрагмент один:
P.S. Константы 3 и 6 в коде заменяются на значения зависящие от длины "запрещённой" подстроки. Оба решения можно обобщить для любых "запрещённых" подстрок. Но не всё так просто.
Упражение 1 Придумайте "запрещённую" строку для которой второе решение будет давать неправильные ответы.
Упражение 2 Покажите что первое решение работает для любых "запрещённых" строк.
Е24.36 Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.
Текстовый файл состоит не более, чем из 1 200 000 символов английского алфавита
Определите максимальное количество идущих подряд символов, среди которых символы Q, R, S в различных комбинациях (с учётом повторений) не стоят рядом.
Для выполнения этого задания следует написать программу.
Досрочный ЕГЭ по информатике 2023 г. Евгений Джобс – задание №2 4