Форум программистов, компьютерный форум CyberForum.ru

Переполнение по времени на больших тестах - C++

Восстановить пароль Регистрация
 
Tattoo-master
2 / 2 / 0
Регистрация: 11.11.2010
Сообщений: 9
12.06.2012, 11:23     Переполнение по времени на больших тестах #1
Максимальное время работы на одном тесте:

1 секунда

Максимальный объем используемой памяти:

64 мегабайт

Слово называется палиндромом, если его первая буква совпадает с последней, вторая – с предпоследней и т.д. Например: "abba", "madam", "x".
Для заданного числа K слово называется почти палиндромом, если в нем можно изменить не более K любых букв так, чтобы получился палиндром. Например, при K = 2 слова "reactor", "kolobok", "madam" являются почти палиндромами (подчеркнуты буквы, заменой которых можно получить палиндром).
Подсловом данного слова являются все слова, получающиеся путем вычеркивания из данного нескольких (возможно, одной или нуля) первых букв и нескольких последних. Например, подсловами слова "cat" являются слова "c", "a", "t", "ca", "at" и само слово "cat" (а "ct" подсловом слова "cat" не является).
Требуется для данного числа K определить, сколько подслов данного слова S являются почти палиндромами.
Формат входных данных
В первой строке вводятся два натуральных числа: N (1 ≤ N ≤ 5 000) – длина слова и K (0 ≤ K ≤ N).
Во второй строке содержится слово S, состоящее из N строчных латинских букв.
Формат выходных данных
Требуется вывести одно число – количество подслов слова S, являющихся почти палиндромами (для данного K).
Примеры
Входные данные

Выходные данные

5 1
abcde
12

3 3
aaa
6


Сколько пытался и так и так, выдает переполнение по времени на больших тестах. Помогите с алгоритмом, пожалуйста.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.06.2012, 11:23     Переполнение по времени на больших тестах
Посмотрите здесь:

C++ Переполнение буфера
C++ Переполнение
C++ Переполнение буфера
Переполнение C++
C++ Задача на переполнение
C++ Переполнение буфера
C++ Переполнение стека
Переполнение массива C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
AnyOne697
 Аватар для AnyOne697
134 / 106 / 5
Регистрация: 22.05.2010
Сообщений: 532
12.06.2012, 20:54     Переполнение по времени на больших тестах #2
Что-то мне подсказывает, что без этого не обойтись. Причём придётся придумать способ динамического хэширования для быстрого извлечения хэша подстрок. Тема интересная, но очень простая - так что Интернеты Вам в помощь.
Yandex
Объявления
12.06.2012, 20:54     Переполнение по времени на больших тестах
Ответ Создать тему
Опции темы

Текущее время: 10:25. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru