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

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

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

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

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

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

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

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

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

@anton78spb · 13.05.2022, 22:25

NebraskKrasnod,

Python
1
2
3
4
from itertools import combinations
s = "aa"
p = "a"
print(len([1 for i in combinations(s, len(p)) if "".join(i) == p]))

@iSmokeJC · 13.05.2022, 22:33

Python
1
print(len(re.findall(p, s)))

Добавлено через 2 минуты
s = "aaaa"
p = "aa"
Сколько здесь вхождений? 2 или 3?

@NebraskKrasnod · 13.05.2022, 22:52 **[ТС]**

Добавлено через 1 минуту
Если введено
ab
aab
Должно вывести 2, а не 1

@iSmokeJC · 13.05.2022, 22:56

Почему?

@NebraskKrasnod · 13.05.2022, 22:59 **[ТС]**

Ну вот это решение антон78спб это правильно.
Видимо то что
aab
В нем 2 ab: Это 0 и 2 элемент, 1 и 2 элемент

@iSmokeJC · 13.05.2022, 23:02

Ну вот видимо задание нужно писать правильно

Добавлено через 1 минуту
В таком случае вот здесь
s = "aaaa"
p = "aa"
все шесть комбинаций, а не две

@NebraskKrasnod · 13.05.2022, 23:02 **[ТС]**

обрыв на тесте
s = "aghjakehgkhaegjkhlkJHSEgkjahrgkjhaerkgj hkerjhgkjehrgkljerhgjkrehgjhrjgjgjrhgjrh gjrghjhgjgjggjgjgjgrhgjhgrjhgjrghjrghjrg hjrghjrghjrgjrgrgjhrjghjrhthwth666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666"

p = "jhke"

Слишком долго выполняется, длина максимальная(около 999 элементов)

@iSmokeJC · 13.05.2022, 23:08

Ну и? Какой ответ на этих данных должен быть?

@NebraskKrasnod · 13.05.2022, 23:10 **[ТС]**

Это я не знаю какой ответ, но такой тест большой есть

@Gdez · 13.05.2022, 23:21

iSmokeJC, 360

@Daivetop · 13.05.2022, 23:36

ответ то какой

@Ivan_bebrovich · 13.05.2022, 23:44

не знаю

@Catstail · 14.05.2022, 07:04

Сообщение от NebraskKrasnod

Слишком долго выполняется

- и неудивительно! Все комбинации - это много (для большой строки)

@Gdez · 14.05.2022, 07:38

В принципе для общего случая не оптимально, но тут можно сократить строку:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from itertools import combinations
s = "aghjakehgkhaegjkhlkJHSEgkjahrgkjh\
aerkgjhkerjhgkjehrgkljerhg jkrehgjhrjg\
jgjrhgjrhgjrghjhgjgjggjgjgjgrhgjhgrjhgj\
rghjrghjrg hjrghjrghjrgjrgrgjhrjghjrht\
hwth666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
66666666666666"
p = "jhke"
#s, p = input(), input()
bad_s = ''.join(set(s) - set(p))
s = s.translate(str.maketrans('', '', bad_s))
s = s[s.find(p[0]):s.rfind(p[-1])+1]
print(s)
print(len([1 for i in combinations(s, len(p)) if "".join(i) == p]))

@iSmokeJC · 14.05.2022, 07:43

Что-то мне подсказывает, что это XY...

@Red white socks · 14.05.2022, 08:09

NebraskKrasnod, Daivetop, Ivan_bebrovich, не знаю, сколько вас тут народа, толпа или один. Этот тест лечится элементарными соображениями:
1) из s можно выкинуть все символы, не входящие в p.
2) из s можно убрать все что слева от первого символа p и справа от последнего символа p (имеются в виду первое слева и первое справа вхождение соответственно)
Это не делает код оптимальным, но приведенный тест точно позволит пройти.
Нетрудно придумать и быстрый алгоритм, используя динамическое программирование, но тут я понимаю, что это неподъемная ноша . Потому что решенные для вас задачи ведут к атрофии вашего мозга. Самостоятельно никаких выводов из приведенных решений вы не делаете и ничему не учитесь.
Пора выходить из этой игры, делать из вас ментального компрачикоса нет никакого желания, по крайней мере у меня.

Добавлено через 7 минут

Сообщение от Red white socks

1) из s можно выкинуть все символы, не входящие в p.
2) из s можно убрать все что слева от первого символа p и справа от последнего символа p (имеются в виду первое слева и первое справа вхождение соответственно)

Пока подбирал цензурные выражения,Gdez уже и реализовал ))

@eaa · 14.05.2022, 10:02

iSmokeJC, нет. средненькая динамика.

@NebraskKrasnod · 14.05.2022, 11:53 **[ТС]**

Да, это прошло. Но тест на 1000 элементов там разные все, это не подходит. TL отлетает. Ну 1000 это максимум

Добавлено через 1 минуту
Может сделать чтобы как Gdez написал, каждый раз разделять строку на эти штуки? И тогда 40 по 25 элементов получится

Добавлено через 19 секунд
вот типа такого :

Сообщение от Gdez

s = "aghjakehgkhaegjkhlkJHSEgkjahrgkjh\
aerkgjhkerjhgkjehrgkljerhg jkrehgjhrjg\
jgjrhgjrhgjrghjhgjgjggjgjgjgrhgjhgrjhgj\
rghjrghjrg hjrghjrghjrgjrgrgjhrjghjrht\
hwth666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
6666666666666666666666666666\
66666666666666"

@eaa · 14.05.2022, 12:25

combinations

NebraskKrasnod, начни изучать динамическое программирование.
это тебе не задачки егэ решать.

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

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .

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

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

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	13.05.2022, 22:52 [ТС]
	Добавлено через 1 минуту Если введено ab aab Должно вывести 2, а не 1 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	13.05.2022, 22:56
	Почему? 1

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	13.05.2022, 22:59 [ТС]
	Ну вот это решение антон78спб это правильно. Видимо то что aab В нем 2 ab: Это 0 и 2 элемент, 1 и 2 элемент 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	13.05.2022, 23:02
	Ну вот видимо задание нужно писать правильно Добавлено через 1 минуту В таком случае вот здесь s = "aaaa" p = "aa" все шесть комбинаций, а не две 1

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	13.05.2022, 23:02 [ТС]
	обрыв на тесте s = "aghjakehgkhaegjkhlkJHSEgkjahrgkjhaerkgj hkerjhgkjehrgkljerhgjkrehgjhrjgjgjrhgjrh gjrghjhgjgjggjgjgjgrhgjhgrjhgjrghjrghjrg hjrghjrghjrgjrgrgjhrjghjrhthwth666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666666666666666666666666666666666 6666666666" p = "jhke" Слишком долго выполняется, длина максимальная(около 999 элементов) 0

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	13.05.2022, 23:08
	Ну и? Какой ответ на этих данных должен быть? 1

@NebraskKrasnod 4 / 6 / 1 Регистрация: 16.04.2022 Сообщений: 139
	13.05.2022, 23:10 [ТС]
	Это я не знаю какой ответ, но такой тест большой есть 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	13.05.2022, 23:21
	iSmokeJC, 360 1

@Daivetop -30 / 1 / 0 Регистрация: 22.02.2021 Сообщений: 47
	13.05.2022, 23:36
	ответ то какой 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	14.05.2022, 10:02
	iSmokeJC, нет. средненькая динамика. 1

@Ivan_bebrovich 7 / 6 / 1 Регистрация: 18.02.2022 Сообщений: 30
	13.05.2022, 23:44
	не знаю 1

@iSmokeJC 19530 / 11067 / 2931 Регистрация: 21.10.2017 Сообщений: 23,294
	14.05.2022, 07:43
	Что-то мне подсказывает, что это XY... 2