Разбиение слова
Отправить решение
Решать в редакторе
Сложность:
40%
Очки:
100 (частичный балл)
Ограничение по времени:
1.0s
Ограничение по памяти:
256M
Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch
Разбиение слова
У Айгерим есть слово s и словарь из d различных слов. Сколькими способами можно записать s как последовательность подряд идущих слов словаря (слова можно использовать повторно)?
Ввод. В первой строке s (1 ≤ |s| ≤ 2000, строчные латинские буквы). Во второй d (1 ≤ d ≤ 50), далее d строк со словами длиной от 1 до 10.
Вывод. Число способов по модулю 10^9 + 7.
Пример
Ввод:
aabaab
3
a
aab
ab
Вывод:
4
Комментарии