ПОШУК ОЛІМПІАДИ - Показати
Шифр

 

 

Дана символьная строка S длины N (0 <= N <= 100) и словарь, который содержит M слов (0 <= M <= 100), длина каждого из которых не превышает N. Строка и слова состоят из символов a, b, ..., z.

Задание

Напишите программу CIPHER, которая определяет наименьшее количество символов, которое необходимо вычеркнуть из заданной строки S, чтобы результирующую строку можно было представить как последовательность слов словаря. Количество использований каждого слова не ограничивается. Считается, что пустую строку можно представить с помощью слов любого словаря.

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

Входные данные

В первой строке входного файла CIPHER.DAT находится два целых числа N и M, разделенных пробелом. Во второй строке находится символьная строка S. В каждой из следующих M строк находится слово словаря.

Пример входного файла

11 5
abafchtdsya
aba
a
bach
dsy
zero

Выходные данные

В единственной строке выходного файла CIPHER.SOL должно находиться натуральное число - минимальное количество вычеркиваний, после которых зашифрованная строка может быть представлена в виде последовательности слов словаря.

Пример выходного файла

2