C++ или Питон

Question

C++ или Питон

Gogrod Ученик (130), закрыт 2 месяца назад

Егор учится читать
Егору в школе задали домашнее задание — выучить наизусть все подстроки строки s
, состоящей из строчных и заглавных букв латинского алфавита.

Но есть проблема: Егор учится в первом классе, и поэтому он знает написание только m
букв латинского алфавита. Если в подстроке встречается буква, написание которой мальчик не знает, то он не сможет выучить написание этой подстроки.

Причем если Егор знает, как пишется какая-то буква в одном регистре, это не значит, что он знает, как пишется эта же буква в другом регистре. Например, если он знает букву B, это не значит, что он знает букву b, и наоборот.

Егору очень интересно, сколько различных слов он сможет выучить. Помогите ему справиться с этой задачей.

Формат входных данных
Первая строка содержит строку s
(1≤|s|≤10
). Гарантируется, что строка s
содержит только строчные и заглавные буквы латинского алфавита.

Вторая строка содержит одно целое число m
(0≤m≤52
) — количество букв, написание которых знает Егор.

Каждая из следующих m
строк содержит один символ — букву, написание которой знает Егор. Гарантируется, что все буквы попарно различны.

Формат выходных данных
Выведите одно целое число — количество различных подстрок строки s
, удовлетворяющих условию задачи.
Ввод
Вывод
abc 6
3
a
b
c

ab 0
2
c
d

aaa 3
2
a
B

Answer 1

Держи на Питоне:

 from re import split

s, m = input(), int(input())
pat = '[^' + ''.join(map(input, ('',) * m)) + ']+'

def allsubs(z):
    return set().union(z[k:k+l+1] for l in range(len(z)) for k in range(len(z) - l))

print(len(set().union(*map(allsubs, split(pat, s)))))

Бьём регулярками на подстроки, содержащие только заданный алфавит. Можно было бы и вручную разбивать, но много возни.
Собираем множества из всех непрерывных подстрок каждой подстроки в одно множество.
Его мощность (len) - это и есть количество слов для этого вашего Егора.

Если бы не нужно было отсеивать дубликаты, то и множества не были бы нужны. Достаточно было посчитать сумму l * (l + 1) // 2 по всем исходным подстрокам (где l - длина подстроки).

Answer 2

Геннадий Сибирский Мудрец (18678) 3 месяца назад

смотря для чего
лучше асемблер

GogrodУченик (130) 3 месяца назад

для сириуса там либо питон либо плюсы