Question

В информатике важную роль играют алгоритмы поиска вхождения подстроки в строку. Например, в строке «АБРАКАДАБРА» подстрока «БРА» встречается два раза, а подстрока из одного символа «А» встречается пять раз. Под количеством вхождений понимается количество способов выбрать несколько подряд идущих символов, совпадающих (в том же порядке) с искомой подстрокой. Найденные вхождения могут пересекаться, то есть один символ может быть составной частью нескольких вхождений. Интерес представляют эффективные алгоритмы поиска вхождений подстроки в строку, то есть алгоритмы, быстро работающие для больших строк. Поэтому мы будем рассматривать в этой задаче случай, когда исходная строка представляет собой многократное повторение какой-то маленькой строки. Например, рассмотрим строку «МАМА» и повторим её 3 раза. Получится строка «МАМАМАМАМАМА». В этой строке подстрока «АМА» встречается 5 раз: «МАМАМАМАМАМА», «МАМАМАМАМАМА», «МАМАMАМАМАМА», «МАМАМАМАМАМА», «МАМАМАМАМАМА». Ответьте на вопросы Если строку «БАОБАБ» повторить 100 раз, то сколько раз в ней будет встречаться подстрока «БА»? Если строку «РЕМАРКА» повторить 100 раз, то сколько раз в ней будет встречаться подстрока «АР»? Если строку «АУАУОАУАУ» повторить 100 раз, то сколько раз в ней будет встречаться подстрока «АУАУ»? Если строку «ОЙОЙ» повторить 100 раз, то сколько раз в ней будет встречаться подстрока «ЙОЙОЙ»? Если строку «А» повторить 100 раз, то сколько в ней раз будет встречаться подстрока «A», повторённая 50 раз? Ответ на это задание запишите в виде пяти чисел, каждое число в отдельной строке — ответы на заданные вопросы именно в таком порядке. Если вы не можете найти ответ на какой-то из пяти вопросов, запишите в этой строке любое натуральное число.

Answer 1

Ответ:

200

198

596

197

50

Объяснение:

Сам долго решал, сейчас расписать решение не смогу, потеряем время оба, удачи с олимпиадой.

Answer 2

Для решения этой задачи, можно воспользоваться следующим методом:

1. Найдем длину искомой подстроки.
2. Рассмотрим, сколько раз данная подстрока помещается в одном повторении строки.
3. Затем умножим это количество на 100 (поскольку строку повторяют 100 раз).
4. Если подстрока "А" повторена 50 раз, то мы просто подсчитываем, сколько раз эта подстрока встречается в одном повторении строки и затем умножаем на 100.

Теперь применим этот метод к вашим вопросам:

1. Длина подстроки "БА" - 2 символа. Она помещается 1 раз в одном повторении строки. Значит, в 100 повторениях строки "БАОБАБ" подстрока "БА" встретится 1 * 100 = 100 раз.

2. Длина подстроки "АР" - 2 символа. Она также помещается 1 раз в одном повторении строки. Значит, в 100 повторениях строки "РЕМАРКА" подстрока "АР" встретится 1 * 100 = 100 раз.

3. Длина подстроки "АУАУ" - 4 символа. Она помещается 2 раза в одном повторении строки (первые два символа и следующие два символа). Значит, в 100 повторениях строки "АУАУОАУАУ" подстрока "АУАУ" встретится 2 * 100 = 200 раз.

4. Длина подстроки "ЙОЙОЙ" - 4 символа. Она также помещается 2 раза в одном повторении строки. Значит, в 100 повторениях строки "ОЙОЙ" подстрока "ЙОЙОЙ" встретится 2 * 100 = 200 раз.

5. Длина подстроки "A"*50 - 50 символов. Она помещается 1 раз в одном повторении строки. Значит, в 100 повторениях строки "А"*50 подстрока "A"*50 встретится 1 * 100 = 100 раз.

Таким образом, ответы на ваши вопросы:

100 100 200 200 100