Question

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

Answer 1

Ответ:

a = "РЕМАРКА"

b = a * 100

kolvo = 0

s = b.find("АР")

for i in range (len(b)):

if s != -1:

 kolvo += 1

 b.replace("АР", "", 1)

print (kolvo)

Объяснение:

на места "РЕМАРКА" и "АР" подставляйте ваши значения

Answer 2

Для решения данной задачи мы можем использовать алгоритм подстрокового поиска Кнута-Морриса-Пратта (алгоритм КМП). Этот алгоритм позволяет эффективно находить все вхождения подстроки в строку.

1) Если строку "БАОБАБ" повторить 100 раз, то подстрока "БА" будет встречаться в ней следующее количество раз: - Подсчитаем количество вхождений подстроки "БА" в самой строке "БАОБАБ": - Первое вхождение: "БАОБАБ" - Второе вхождение: "БАОБАБ" - Общее количество вхождений в строке "БАОБАБ": 2 - Так как строка "БАОБАБ" повторяется 100 раз, общее количество вхождений подстроки "БА" будет равно 2 * 100 = 200.

2) Если строку "РЕМАРКА" повторить 100 раз, то подстрока "АР" будет встречаться в ней следующее количество раз: - Подсчитаем количество вхождений подстроки "АР" в самой строке "РЕМАРКА": - Первое вхождение: "РЕМАРКА" - Второе вхождение: "РЕМАРКА" - Общее количество вхождений в строке "РЕМАРКА": 2 - Так как строка "РЕМАРКА" повторяется 100 раз, общее количество вхождений подстроки "АР" будет равно 2 * 100 = 200.

3) Если строку "АУАУОАУАУ" повторить 100 раз, то подстрока "АУАУ" будет встречаться в ней следующее количество раз: - Подсчитаем количество вхождений подстроки "АУАУ" в самой строке "АУАУОАУАУ": - Первое вхождение: "АУАУОАУАУ" - Второе вхождение: "АУАУОАУАУ" - Общее количество вхождений в строке "АУАУОАУАУ": 2 - Так как строка "АУАУОАУАУ" повторяется 100 раз, общее количество вхождений подстроки "АУАУ" будет равно 2 * 100 = 200.

4) Если строку "ОЙОЙ" повторить 100 раз, то подстрока "ЙОЙОЙ" будет встречаться в ней следующее количество раз: - Подсчитаем количество вхождений подстроки "ЙОЙОЙ" в самой строке "ОЙОЙ": - Первое вхождение: "ОЙОЙ" - Второе вхождение: "ОЙОЙ" - Общее количество вхождений в строке "ОЙОЙ": 2 - Так как строка "ОЙОЙ" повторяется 100 раз, общее количество вхождений подстроки "ЙОЙОЙ" будет равно 2 * 100 = 200.

5) Если строку "А" повторить 100 раз, а подстроку "A" повторить 50 раз, то количество вхождений подстроки "A", повторенной 50 раз, в этой строке будет равно 100.

Таким образом, ответы на заданные вопросы будут следующими:

200 200 200 200 100