images/home.png Начало
Имя: Пароль:
Зарегистрироваться
Восстановить пароль
25/04/2024 23:14:06

printРабочее место участника

Выбрать соревнование Задачи Послать решение Результаты проверки Статистика по задачам Вопросы и ответы Результаты соревнования Состояние сервера Изменить данные Управление командой Помощь

printЗадачи

831. Лишние буквы

Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Дана символьная строка `S` длины `N` (`0\ ≤\ N\ ≤\ 100`) и словарь, который содержит `M` слов (`0\ ≤\ M\ ≤\ 100`), длина каждого из которых не превышает `N`. Строка и слова состоят из символов a, b, …, z.
Напишите программу, которая определяет наименьшее количество символов, которое необходимо вычеркнуть из заданной строки `S`, чтобы результирующую строку можно было представить как последовательность слов словаря. Количество использований каждого слова не ограничивается. Считается, что пустую строку можно представить с помощью слов любого словаря.
В первой строке входного файла находится два целых числа `N` и `M`, разделенных пробелом. Во второй строке находится символьная строка `S`. В каждой из следующих `M` строк находится слово словаря.
В единственной строке выходного файла должно находиться натуральное число – минимальное количество вычеркиваний, после которых зашифрованная строка может быть представлена в виде последовательности слов словаря.

Пример ввода

11 5
abafchtdsya
aba
a
bach
dsy
zero

Пример вывода

2
Примечание: Строка в примере после вычеркивания лишних букв f и t примет вид abachdsya (было сделано два вычеркивания: abafchtdsya), и может быть представлена как последовательность следующих слов: a, bach, dsy, a.
XIV Всеукраинская олимпиада по информатике, 2001
loading