Сколько раз p входит в s в качестве подпоследовательности?

@NebraskKrasnod · Регистрация: 16.04.2022

Студворк — интернет-сервис помощи студентам

Вам заданы строки s и p, состоящие из строчных латинских символов.

Сколько раз pвходит в s в качестве подпоследовательности?

Сначала вводится s, потом во второй строке p.

Пример1:
Ввод:
aa
a
Вывод:
2

--------------
Пример2:
Ввод: abcbdab
bcdb
Вывод:
1

(составлено из символов с индексами 1, 2, 4, 6 соответственно, индексация начинается с нуля)

@NebraskKrasnod · 14.05.2022, 13:51 **[ТС]**

надо еще вывести ответ по модулю (10 в 9 степени + 7)

Возможно

Python
1
2
3
4
5
6
7
8
9
10
s = input()
p = input()
e = [[int(i == 0) for i in range(len(p) + 1)] for j in range(len(s) + 1)]
for i in range(1, len(s) + 1):
    for j in range(1, len(p) + 1):
        e[i][j] = e[i - 1][j]
        if s[i - 1] == p[j - 1]:
            e[i][j] += e[i - 1][j - 1]
ara = e[-1][-1]
print(ara & 1000000007)

Но на 45 тесте отлетает, причем даже без этого модуля все было хорошо до 74 теста.
странно что-то

Добавлено через 12 минут
"Так как ответ может быть слишком большим, выведите его по модулю (остаток от деления) 10**9+7"

@eaa · 14.05.2022, 14:31

NebraskKrasnod, ну считай по модулю. в чем проблема? причем тут "побитовое И"?

@NebraskKrasnod · 14.05.2022, 16:55 **[ТС]**

Проблема что с модулем неверно на том тесте, где без модуля все было правильно. А в условии сказано что с модулем сделаьь

Добавлено через 3 минуты
Вот хз чо делать, видимо в модуль как-то не так считаю

Добавлено через 2 часа 5 минут
Чо делать помогите решить по модулю вывести

@eaa · 14.05.2022, 18:03

NebraskKrasnod, выведи по модулю.

@NebraskKrasnod · 14.05.2022, 18:20 **[ТС]**

А как

@Enldar_Spb78 · 17.05.2022, 22:36

Тоже интересует эта задача

Добавлено через 1 минуту
для 1000 элементов долго будет выполняться, еще если в модуль это считать, хз что делать

@ResDT · 28.06.2022, 16:24

Одним проходом.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
s = input()
p = input()
count = 0
 
 
for place in range(len(s) - len(p) + 1):
    word = s[place:place + len(p)]
 
    if word == p:
        count += 1
 
 
print(count % (10**9 + 7))

@eaa · 28.06.2022, 16:26

Подпоследовательности это не подстрока

@ResDT · 28.06.2022, 16:35

Одним проходом.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
s = input()
p = input()
count = 0
 
 
for place in range(len(s) - len(p) + 1):
    word = s[place:place + len(p)]
 
    if word == p:
        count += 1
 
 
print(count)

Добавлено через 4 минуты
eaa, а, там выборку делать? Ну и порнуха

Новые блоги и статьи Все статьи Все блоги /
Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .	Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .
Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .	Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139

	Сколько раз p входит в s в качестве подпоследовательности? 13.05.2022, 22:08. Показов 4896. Ответов 28 Метки нет (Все метки) Вам заданы строки s и p, состоящие из строчных латинских символов. Сколько раз pвходит в s в качестве подпоследовательности? Сначала вводится s, потом во второй строке p. Пример1: Ввод: aa a Вывод: 2 -------------- Пример2: Ввод: abcbdab bcdb Вывод: 1 (составлено из символов с индексами 1, 2, 4, 6 соответственно, индексация начинается с нуля) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.05.2022, 14:31
	NebraskKrasnod, ну считай по модулю. в чем проблема? причем тут "побитовое И"? 0

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	14.05.2022, 16:55 [ТС]
	Проблема что с модулем неверно на том тесте, где без модуля все было правильно. А в условии сказано что с модулем сделаьь Добавлено через 3 минуты Вот хз чо делать, видимо в модуль как-то не так считаю Добавлено через 2 часа 5 минут Чо делать помогите решить по модулю вывести 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.05.2022, 18:03
	NebraskKrasnod, выведи по модулю. 0

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	14.05.2022, 18:20 [ТС]
	А как 0

@Enldar_Spb78 2 / 2 / 0 Регистрация: 17.05.2022 Сообщений: 33
	17.05.2022, 22:36
	Тоже интересует эта задача Добавлено через 1 минуту для 1000 элементов долго будет выполняться, еще если в модуль это считать, хз что делать 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	28.06.2022, 16:26
	Подпоследовательности это не подстрока 0

Опции темы