М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
darabajkova4770
darabajkova4770
17.12.2022 12:44 •  Информатика

Уазизхана есть строка s. его интересует сколько есть подстрок четной длины у строки s, которые являются палиндромами. одинаковые подстроки начинающие с разных позиций считаются разными. формат входных данных единственная строка входного файла содержит одну строку s состоящее из строчных букв алфавита (1 < = длина s < = 100000). формат выходных данных выведите ответ к .

👇
Ответ:
NeZnayVsego
NeZnayVsego
17.12.2022
Наивный алгоритм: используя два вложенных цикла, проверить все подстроки, являются ли они палиндромами. Такой алгоритм будет работать O(|S|^2), что при ограничении |S| <= 10^5 потребует примерно 10^10 / 2 сравнений, что достаточно долго.

Оптимизация: в центре у палиндрома четной длины всегда пара одинаковых символов. Их можно найти, а затем увеличивать длину до тех пор, пока это возможно. Плюс этого наблюдения в том, что если пара попадется не в центре, то максимальная длина подстроки-палиндрома с центром в этой паре, будет ограничена сверху. Однако в худшем случае (все символы одинаковы) всё равно придется произвести немалое число сравнений.

Однако задачу можно решить и за линейное время. Например, существует алгоритм Манакера, основанный на том, что можно использовать информацию, что часть строки является палиндромом. А именно, если в длинную-длинную строку-палиндром входит другая подстрока-палиндром, то можно не начинать проверку заново, а использовать уже имеющуюся информацию.

Пример 1: "длинная" подстрока-палиндром:
cbbaabbaabbc
в которой известна подстрока-палиндром. Тогда в строке есть симметричная подстрока-палиндром:
cbbaabbaabbc
Пример 2: "длинная" подстрока палиндром:
bbaabbaabbaa
Зная, что в ней есть подстрока-палиндром
bbaabbaabbaa,
можно явные сравнения для подстроки с центром в
bbaabbaabbaa
начинать уже с 
bbaabbaabbaa

Если не хочется писать самостоятельно, алгоритм Манакера легко находится.
4,4(99 оценок)
Открыть все ответы
Ответ:
fida2
fida2
17.12.2022
Для удобства вычислений переведём размер сканируемого изображения в дюймы: 20,32 × 20,32 (см) = 8 × 8 (inch).

Сначала найдём количество пикселей по горизонтали, по вертикали, затем общее количество пикселей, исходя из разрешающей сканера. Зная, что каждый пиксель кодируется 4 битами, найдём объём памяти, необходимый  для хранения графической информации, что и будет являться информационным объёмом файла.

1)    600 × 8 = 4800 (px) – количество пикселей по горизонтали.

2)    1200 × 8 = 9600 (px) – количество пикселей по вертикали.

3)    4800 × 9600 = 46 080 000 (px) – всего пикселей.

4)    46 080 000 × 4 = 184 320 000 (bit) = 22 500 (KB)

ответ: полученный графический файл будет иметь объём 22 500 килобайт.
4,5(21 оценок)
Ответ:
Arianna779
Arianna779
17.12.2022
Содержание понятия — это совокупность существенных и отличительных признаков предмета, качества или множества однородных предметов, отражённых в этом понятии, поскольку с точки зрения логики всякое понятие имеет содержание и объём. например, содержанием понятия «коррупция» является совокупность двух существенных признаков: «сращение государственных структур со структурой преступного мира» и «подкуп и продажность общественных и политических деятелей, государственных чиновников и должностных лиц». о содержании понятия нельзя говорить в отрыве от его объёма. объёмом понятия называется множество обобщённых в нём предметов. например, под объёмом понятия «товар» подразумевается множество всех изделий, предлагаемых рынку как сейчас, так и в прошлом или в будущем. а чтоб понятнее: род - цветок, фрукт, овощ, буква, цифра, орудие, прибор, животное, насекомое, металл, орган, подросток, дом, день, военный, вид - школьник, лодка, олово, почки, морковь, микроскоп, два, фиалки, сержант, топор, груши, "у", тюлень, резиновая лодка, оса, деревянный дом, зимний день. кажется так. вот род цветок, а вид фиалка. или род овощ, а вид морковь. в род входит класс. цветок - фиалка фрукт - груши овощ - морковь буква - у цифра - 2 орудие - топор прибор - микроскоп животное - тюлень насекомое - оса
4,4(42 оценок)
Это интересно:
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ