сервис вопросов и ответовУ Азизхана есть строка S. Его интересует сколько есть подстрок четной длины у строки S, которые являются палиндромами. Одинаковые подстроки начинающие с
5-9 класс|
|
разных позиций считаются разными.
Формат входных данных
Единственная строка входного файла содержит одну строку S состоящее из строчных букв английского алфавита (1 <= длина S <= 100000).
Формат выходных данных
Выведите ответ к задаче.
Помагите плиз
Vlad2555
04 дек. 2013 г., 5:24:52 (10 лет назад)
Polozova0207
04 дек. 2013 г., 7:03:40 (10 лет назад)
Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. Такой алгоритм будет работать O(|S|^2), что при ограничении |S| <= 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго.
Оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. Их можно найти, а затем увеличивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений.
Однако задачу можно решить и за линейное время. Например, существует алгоритм Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию.
Пример 1: "длинная" подстрока-палиндром:
cbbaabbaabbc
в которой известна подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром:
cbbaabbaabbc
Пример 2: "длинная" подстрока палиндром:
bbaabbaabbaa
Зная, что в ней есть подстрока-палиндром
bbaabbaabbaa,
можно явные сравнения для подстроки с центром в
bbaabbaabbaa
начинать уже с
bbaabbaabbaa
Если не хочется писать самостоятельно, алгоритм Манакера легко находится.
Ответить
Другие вопросы из категории
Под буквой б)
Нужно просто заполнить таблицу.... Я под буквой б) не понимаю, что нужно сделать , помогите!!!!
ПОМОГИТЕ!!!!!!!!!!
ВВЕДИТЕ ТРИ ЧИСЛА a,b,c. Найдите сумму двух наибольших из них.
Читайте также
Программа на Pascal ABC. С клавиатуры вводится маленькими русскими буквами строка, необходимо для каждого символа вывести, а) сколько раз его употребили и
б) частоту употребления (отношение а к длине строки, не считая пробелов).
Примечание 1. Выводить только для маленьких русских букв, пробелы не трогать.
Пример. Вводится строка 'раз два три'. нужно вывести:
р - 2 раза, ч.у - 0.27 //Округление до сотых
... Ну и так далее. Два раза один и тот же символ не выводить!
Вводить новые переменные можно в любом количестве.
1) Сколько байт (без кавычек) содержит фраза «Сегодня 10 октября 2013 г.»?
2) Сколько байт (килобайт) занимает одна страница текста, если в одной строке помещается 60 символов, а на странице – 40 строк? Каков объем одной книги, состоящей из 100 подобных страниц?
3) Терабайтник - это внешний жесткий диск, который подключается к компьютеру через разъем USB, и имеет емкость 1 террабайт. В инструкции по его применению написано, что на этот диск может поместиться 250 тыс. музыкальных файлов или 285 тыс. фотографий. Каковы по мнению производителей этого устройства размер одного музыкального файла и размер одной фотографии?
4) Сколько подобных музыкальных файлов может поместиться на одном CD-диске размером 700 мегабайт?
5) Сколько подобных фотографий может поместиться на флешке размером 4 гигабайта?
От слова ТЕЛЕФОНОГРАММА получить слово ГРАММОФОН. на ппаскале, с помощью удаления, вставки и копиравания, еще вычислить сколько символов в строке.
Строку ввести с клавиатуры. (Используется функция нахождения длины строки length). пожалуйста очень надо
1. Загадано число из промежутка от 1 до 256. Какое количество информации необходимо для угадывания числа из этого промежутка?
2. В корзине лежат 4 красных и 28 чёрных кубика. Какое количество информации несёт сообщение о том, что достали красный кубик?
3. При составлении сообщения использовали 16-символьный алфавит. Каким будет информационный объём такого сообщения, если оно содержит 5120 символов?
4. Сообщение занимает 5 страниц. На каждой странице по 80 строк. В каждой строке по 40 символов. Найдите информационный объём такого текста, если при его составлении использовали 256-символьный алфавит.
5. Выразите 32 Мбайт в битах и 16 Гбайт в байтах.
6. Решите уравнение а) 4 Гбайта=2^x байт=2^y бит; б) 8^x Кбайт=32 Гбайт
7. Модем передаёт данные со скоростью 7680 бит/с. Передача текстового файла заняла 1,5 мин. Определите, сколько страниц содержал переданный текст, если известно, что он был представлен в 16-битной кодировке Unicode, а на одной странице - 400 символов.
8. Какой формат кода применим для кодировки алфавита в котором 299 символов?
9. Дан алфавит { # D W K J % * + = > $ @ & ; }. Закодируйте его в минимально возможном формате байта.
10. Некоторое устройство передаёт в секунду один из семи сигналов. Сколько различных сообщений длиной в 3с можно передать при помощи этого устройства?
Срочно, высокий балл, первому лучший ответ
Подсчитать сколько раз в текстовой строке S встретится подстрока S1.
Пример работы правильной программы:
Исходные данные
строка S:
четыре черненьких чумазеньких чертенка чертили черными чернилами чертеж
подстрока S1:
черн
Ответ:
подстрока "черн" в строке "четыре черненьких чумазеньких чертенка чертили черными чернилами чертеж" встречается 3 раз(а).
Подправить код, на данный момент при таком раскладе выдает ответ 0.
Вы находитесь на странице вопроса "У Азизхана есть строка S. Его интересует сколько есть подстрок четной длины у строки S, которые являются палиндромами. Одинаковые подстроки начинающие с", категории "информатика". Данный вопрос относится к разделу "5-9" классов. Здесь вы сможете получить ответ, а также обсудить вопрос с посетителями сайта. Автоматический умный поиск поможет найти похожие вопросы в категории "информатика". Если ваш вопрос отличается или ответы не подходят, вы можете задать новый вопрос, воспользовавшись кнопкой в верхней части сайта.