Количество способов составить строку.

[Deals]

Здравствуйте,программеры. Помогите решить программу на С++.

Условие (краткое):Входной файл содержит несколько тестов.Дана строка, длина которой не более 300 000. Вторая строка содержит число S, 1<=S<=4000. Каждая из следующих S строк содержит одно слово из набора. Каждое слово не более 100 символов. Все буквы имеют нижний регистр и нет одинаковых слов.

Существует пустая строка между последовательными тестов.
Необходимо идти до конца файла.

Проблема заключается в следующем: слово должно быть разделено на небольшие кусочки таким образом, что каждая часть из некоторого заданного набора слов. Для слова и множество слов, должны подсчитать количество способов данное слово можно разделить, используя слова в наборе.

Для каждого теста вывести количество способов.